BOJ_14225_부분수열의 합 (Java)

[Silver I] 부분수열의 합 - 14225

문제 링크

### 성능 요약

메모리: 16396 KB, 시간: 124 ms

### 분류

브루트포스 알고리즘

### 제출 일자

2025년 3월 13일 15:23:25

### 문제 설명

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

문제 풀이

코드

 /**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, S[];
    static boolean[] visited, isNum;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_14225_부분수열의합/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.parseInt(br.readLine());
        S = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            S[i] = Integer.parseInt(st.nextToken());
        }

        visited = new boolean[N];
        isNum = new boolean[100000*20 + 1];

        dfs(0, 0);
        for(int i = 0; i < isNum.length; i++) {
            if(!isNum[i]) {
                System.out.println(i);
                break;
            }
        }
        br.close();
    }

    private void dfs(int depth, int sum) {
        if(depth == N){
            isNum[sum] = true;
            return;
        }

        dfs(depth + 1, sum + S[depth]);
        dfs(depth + 1, sum);
    }


}