[1182] 부분수열의 합

🔗 문제 링크

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

🔍 문제 설명

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

⚠️ 제한사항

• 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000)

• 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.

• 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

🗝 풀이 (언어 : Java)

처음에 순서를 지키고 연속된 부분 수열을 구하는 줄 알았는데, 연속되지 않아도 되고, 같은 숫자라도 다른 위치에 있는 숫자면 다른 케이스로 취급해야했다. 백준 문제는 이런 것들을 예시나 설명하는게 너무 불친절한 것 같다; 또 전 순서까지 수열을 만든 것이 정답이라 카운트했는데, 다음 숫자를 포함하지 않는 경우 다시 정답처리된다. 하지만 이것은 중복이기 때문에 한번만 카운트해줘야 한다. 그래서 중간에 정답여부를 체크하지 않고 수열의 끝숫자까지 가서 정답을 체크했다. 이렇게해도 중간에 포함 or 포함하지 않는 경우를 모두 거쳐서 오기 때문에 모든 케이스에 대해 체크가 가능하다.단 이렇게 하면 처음에 s가 0이고 원소 하나도 포함 안했는데 sum이 0부터 시작해서 정답으로 카운트되는 경우가 예외로 생기기 때문에 따로 -1 처리해주었다.

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

class Main {
    private static int answer = 0;

    private void dfs(int n, int s, int[] arr, int idx, int sum) {
        // 해당 경우의 수의 숫자들이 완성되면 총합이 정답과 같은 경우 카운트,
        if (idx == n-1) {
            if (sum == s)
                answer++;
            return;
        }
        // 해당 인덱스 숫자 택하지 않은 경우
        dfs(n, s, arr, idx+1, sum);
        // 해당 인덱스 숫자 택한 경우
        dfs(n, s, arr, idx+1, sum + arr[idx+1]);
    }

    private void subSequence(int n, int s, int[] arr) {
        // 첫번째 원소 경우의 수에 포함 안한 경우 & 포함한 경우로 시작
        dfs(n, s, arr, 0, 0);
        dfs(n, s, arr, 0, arr[0]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), s = Integer.parseInt(st.nextToken());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        br.close();
        main.subSequence(n, s, arr);
        // s가 0이고 모든 수열 숫자 사용안하고 sum이 0인 경우는 정답이 아니지만 카운트 되므로 제외
        System.out.print((s == 0) ? answer-1 : answer);
    }
}