[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);
   }


}