[BOJ] 1182 - 부분수열의 합 JAVA

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력 1

5 0

-7 -3 -2 5 8

예제 출력 1

1

 

 

 

 

 

 

 

풀이 1. (틀린 코드)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int N, S, ans;
    static int[] arr = null;
    static boolean[] check = null;

    public static void dfs(int last, int sum) {
        if(sum == S) {
            ans += 1;
        }
        for(int i = 0; i < N; i++) {
            if(!check[i] && arr[i] >= last) {
                check[i] = true;
                dfs(arr[i], sum + arr[i]);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        arr = new int[N];
        check = new boolean[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < N; i++) {
            check[i] = true;
            dfs(arr[i], arr[i]);
            check[i] = false;
        }
        System.out.println(ans);
    }
}

 

33%에서 시간 초과.

 

지금까지의 브루트 포스 문제들과는 조금 다르다.

 

지금까지의 문제들은 거의 두 경우로 나뉘어졌다.

1.  2차원 배열을 탐색하는 방식.

2. 특정 dept를 목표로하여 탐색하는 방식.

 

그런데 이 문제는 목표로 하는 숫자의 합을 찾아야 한다.

음수를 더하는 경우도 있기 떄문에 if(sum == S) 에 들어와도 ans += 1을 할 뿐 return 하지는 않고 그대로 탐색을 이어나가야 한다.

 

즉, N의 최대값이 20이므로  20까지 dept를 갖는 DFS를 다 수행해야 한다는 것.

목표 dept를 1로 하여 DFS,

목표 dept를 2로 하여 DFS,

목표 dept를 3으로 하여 DFS,

.
.

.

목표 dept를 20으로 하여 DFS,

 

그렇기 때문에 시간초과가 발생하는 듯 하다.

 

 

 

 

 

 

풀이 2. (정답 코드)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int N, S, ans;
    static int[] arr = null;

    public static void dfs(int dept, int sum) {
        if(dept == N) {
            if(sum == S) {
                ans += 1;
            }
            return;
        }
        dfs(dept + 1, sum + arr[dept]);  // 해당 인덱스를 포함
        dfs(dept + 1, sum);  // 해당 인덱스를 포함하지 않음
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0);
        if(S == 0) {  // S == 0일 경우 공집합도 체크하게 됨. 공집합에 대한 정답 1 제거.
            ans -= 1;
        }
        System.out.println(ans);
    }
}

 

목표 dept를 N으로 두고 배열의 끝까지 탐색을 실시한다.

탐색 과정에서 해당 원소를 포함할 것인지 포함하지 않을 것인지에 대한 경우로 재귀를 실시한다.

 

 

 

 

근데 이것도 결국 모든 경우를 따지게 되는 거 아닌가..?

아.. 모르겠다...

 

->

 

순서를 중요시하는 조합이 아니라 어떤 수가 포함되느냐 아니냐만 따지면 되느냐가 중요하다는 게 차이인 듯.

 

하나의 원소에 대해서 그 수를 포함하느냐 포함하지 않느냐 두 가지 경우가 나오기 때문에 O(2^N)으로 처리가 가능하다.

(2 ^ 20 = 약 1백만)