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

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

1182번: 부분수열의 합

https://sudeky.tistory.com/126

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

기존에 풀던 방식으로 풀경우 아래와 같은 형태로 탐색을 하게된다.

 

 

기존에 15번을 거쳐야 완성되던 피라미드 형태에서 

{10} + {20},{10,20} + {30}{10,30}{20,30}{10,20,30}으로 8번만 거치면 완성되는 형태로 바꿀수있다.

시간이 매우 단축된다.

 

한번구한것은 다시 구하지않기 위해서

d[] 배열에 부분집합을 저장하고 저장되어있는 배열을 활용하여서 추가만 하는 방법으로 진행한다.

그리고 위의 점화식을 사용해서 for문으로 만들경우 아주쉽게 부분집합을 출력가능하다.

package bruteforce;

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

public class _1182_dp {

    static StringBuilder sb = new StringBuilder();
    static String d[] = new String[100];
    public static void main(String args[]) throws IOException, NumberFormatException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        String n[] = br.readLine().split(" ");
        int count=1;
        d[0] = "";
        for(int i = 0 ; i < num ; i++){
               for(int j = 0 ; j < 1 << i ; j++){
                    d[count] = d[j] +" " +n[i];
                    count++;
               }
        }

        for(int i = 0 ; i < 1 << num ; i++){
            System.out.println(d[i]);
        }


    }
}

 

위방식으로 해당문제를 풀경우

 

package bruteforce;

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

public class _1182_dp {

    static StringBuilder sb = new StringBuilder();
    static int d[];
    static int n[] = new int[21];
    static int dap=0;
    public static void main(String args[]) throws IOException, NumberFormatException{
        
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int hap = sc.nextInt();
        for (int i = 0; i < num; i++) {         
            n[i] = sc.nextInt();
        }
        d = new int[1 << num];

        int count=1;
        d[0] = 0;
        for(int i = 0 ; i < num ; i++){
               for(int j = 0 ; j < 1 << i ; j++){
                    d[count] = d[j]+n[i];
                    if(d[count] == hap) dap++; 
                    count++;
               }
        }

        System.out.println(dap);


    }
}

 

몇개만 수정하면 답이 완성된다.

 

 

백준문제풀이Github : 

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

sdk0213/baekjoon-study