자바(Java) 백준 14225 부분 수열의 합 풀이

문제

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

14225번: 부분수열의 합

풀이

수열의 정의에 대해서 정확히 알고 있어야 헷깔리지 않습니다. 처음에 풀 때 연속된 순서로 존재하는 값들을 부분 수열이라고 생각했는데 잘못 생각했네요..
ex) 1, 2, 3, 4 -> (1, 2, 3), (2, 3, 4), (1, 2)
이런 것들만 되는 줄 알았는데 조합이라고 생각하면 될거 같습니다.

따라서, dfs를 사용해서 간단하게 풀었습니다. dfs를 사용해서 수들의 합 경우의 수를 다 구하게 되는데 체크 배열을 하나 두고 풀면 좀 더 간단하게 풀 수 있네요 ㅎㅎㅎ

코드

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

public class Main {

    static int n;
    static int[] arr;
    // 최대 값은 100000 * 20이기 때문에 넉넉하게 설정
    static int[] resArr = new int[2500000];

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

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0);

        // 체크 되지 않은 가장 작은 자연수 값을 구합니다.
        for (int i = 1; i < 2500000; i++) {
            if (resArr[i] == 0) {
                System.out.println(i);
                break;
            }
        }
    }

    public static void dfs(int cur, int sum) {
        if (cur == n) {
            // 구해진 값을 체크
            resArr[sum] = 1;
            return;
        }

        // 모든 경우의 수 구하기
        dfs(cur + 1, sum + arr[cur]);
        dfs(cur + 1, sum);
    }
}