(Baekjoon) brute-force - (1) 부분수열의 합( + 부분집합 출력)

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

우선 부분수열의 합을 구하기전에

부분집합을 출력하는방법을 할줄 알아야한다.

부분집합을 출력하는방법은 visited로 표현할수있는데

예를들어서 1,2,3,4 를 가지고 부분집합을 구성할때

visited가 1000 이라면 1

visited가 1110 이라면 123

visited가 0011 이라면 34

... 의 식으로 표현하면 모든 부분집합을 표현할수 있다.

 

package bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;



public class _1182{

    static int n[] = new int[4];
    static int visited[] = new int[4];
    static int count;
    static void dfs(int depth){
        if(depth == count){
            for (int i = 0; i < 4; i++) {
                if (visited[i] == 1)
                    System.out.print(n[i]);
            }
            System.out.println();
            return;
        }

        visited[depth] = 1;
        dfs(depth+1);
        visited[depth] = 0;
        dfs(depth+1);
        

        
    }

    public static void main(String args[]) throws IOException{

        Scanner sc = new Scanner(System.in);
        count = 4;
        for(int i = 0 ; i < 4 ; i++)
             n[i] = sc.nextInt();

        dfs(0);
        sc.close();



    }
}

아래 사진과 같이 탐색을 한다.  탐색도중에 깊이가 4라면 출력하고 return으로 돌아간다.

 

이러한 방식과

 

package bruteforce;

import java.io.IOException;
import java.util.Scanner;



public class _1182{

    static int n[] = new int[21];
    static String a;
    static StringBuilder sb = new StringBuilder();
    static int count;
    static void dfs(String str,int depth){
        if(depth == count){
            if(!str.equals(""))
            sb.append(str+"\n");
            return;
        }
        dfs(str+n[depth]+"",depth+1);
        dfs(str+"",depth+1);
        

        
    }

    public static void main(String args[]) throws IOException{

        Scanner sc = new Scanner(System.in);
        count = sc.nextInt();
        for(int i = 0 ; i < count ; i++)
             n[i] = sc.nextInt();

        dfs("",0);
        System.out.println(sb.toString());
        sc.close();



    }
}

 

윗단계로 올라갈때마다 str에 저장하고 마지막에 stringbuilder로 출력을 하는 방식도 있다.

 

여기에서 간단히

 

이런식으로만 처리해준다면 쉽게 답을 얻을수 있다.

 

package bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _1182{

    static int n[];
    static int dap=0;
    static int s;
    static int count;
    static void dfs(int hap,int depth,int gong){
        if(depth == count){
            if( hap == s && gong != count){

                dap++;
            }
            return;
        }
        dfs(hap+n[depth],depth+1,gong);
        dfs(hap+0,depth+1,gong+1);
        
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String q[] = br.readLine().split(" ");
        count = Integer.parseInt(q[0]);
        s = Integer.parseInt(q[1]);
        n = new int[30];
        q = br.readLine().split(" ");
        for(int i = 0 ; i < count ; i++)
            n[i] = Integer.parseInt(q[i]);

        dfs(0,0,0);
        System.out.println(dap);
       



    }
}

 

 

dfs(int hap, int depth, int gong)

hap = 값더해주면서 stack쌓기

depth = 깊이 확인

gong = 공집합확인

(예를들어서 어떠한 값도 추가하지 않을경우 hap = 0 이 나오는데 답이 0 인경우에는 잘못카운팅할수있음)

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study