[Java] 백준 1182번 부분수열의 합

문제

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

입력

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

출력

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

---

풀이

주의! 부분수열은 substring이 아니다.

부분 수열은 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열이다.
예를 들어, (-7, -3, -2, 5, 8)의 부분 수열로 (-3, 5, 8)을 말할 수 있다.

즉, 조합을 이용하여 풀어야 한다.
조합은 recursive call로 구현하였다.

첫번째 시도 - 실패

public static void selectSubsequence(int sum, int[] arr, int i){
    for(int j=i+1; j<arr.length; j++){
        sum += arr[j];
        selectSubsequence(sum, arr, j);
        if(sum == input)
            count++;
        sum -= arr[j];
    }
}

public static void main(String[] args) {
    ...
    for(int i=0; i<arr.length; i++){
        int sum = arr[i];
        selectSubsequence(sum, arr, i);
    }
    ...
}

문제점

이 코드는

5 1
1 4 3 2 0

을 입력했을 때
{1}, {1, 0}이 조건을 만족하므로 2를 출력해야 하는데, 1을 출력하였다.

부분수열의 원소가 1개일 때, 원소의 합과 주어진 정수 S가 같은지 확인하는 문장이 빠져있었던 것이 문제였다.

두번째 시도 - 성공

public static void selectSubsequence(int sum, int[] arr, int i){
    for(int j=i+1; j<arr.length; j++){
        sum += arr[j];
        selectSubsequence(sum, arr, j);
        if(sum == input)
            count++;
        sum -= arr[j];
    }
}

public static void main(String[] args) {
    ...
    for(int i=0; i<arr.length; i++){
        int sum = arr[i];
        selectSubsequence(sum, arr, i);
        if(sum == input)
            count++;
    }
    ...
}

main 함수의 for문 안에 if(sum == input) count++; 문장을 넣어
원소가 1개일 때도 문제의 조건을 만족하는지 검사하도록 수정하였다.

전체 코드

import java.util.*;

public class Main {
    static int count = 0;
    static int input = 0;

    public static void selectSubsequence(int sum, int[] arr, int i){
        for(int j=i+1; j<arr.length; j++){
            sum += arr[j];
            selectSubsequence(sum, arr, j);
            if(sum == input)
                count++;
            sum -= arr[j];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        input = sc.nextInt();

        int [] arr = new int[size];
        for(int i=0; i<size; i++)
            arr[i] = sc.nextInt();

        for(int i=0; i<arr.length; i++){
            int sum = arr[i];
            selectSubsequence(sum, arr, i);
            if(sum == input)
                count++;
        }

        System.out.println(count);
    }
}