[백준] 14225 부분수열의 합 - JAVA

문제

수열 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의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

생각

부분집합 합을 어떻게 구할까?

dfs를 이용하여 구해준다. 여기서 중요한점은 수열S에서의 원소를 합해주는 경우와 그렇지 않는 경우를 나눠서 dfs를 재귀 호출해줘야 한다.

합으로 나올 수 없는 최솟값은 어떻게 구할까?

부분집합의 합을 인덱스로 가지는 boolean배열을 만들어 주고 i=1부터 isUse의 길이만큼 반복문을돌면서 false인 인덱스를 찾게 되면 젤 처음 false를 가지는 인덱스가 최솟값이 된다. 이때 배열의 길이는 100000 x 20+1인데 S를 이루고있는 수는 100,000보다 작거나 같은 수이고 S의 최대크기는 20이므로 합으로 나올 수 있는 최댓값은 100000 x 20이기 때문이다.

구현

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

public class Main {
  static int[] num;
  static boolean[] isVisit;
  static boolean[] isUse;
  static int N;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    num = new int[N];
    isVisit = new boolean[N];
    isUse = new boolean[100000*20 + 1];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i=0; i<N; i++) {
      num[i] = Integer.parseInt(st.nextToken());
    }
    dfs(0,0);
    for(int i=1; i<isUse.length; i++) {
      if(!isUse[i]) {
        System.out.println(i);
        break;
      }
    }
  }
  public static void dfs(int depth,int sum) {
    if(depth == N) {
      isUse[sum] = true;
      return;
    }
    dfs(depth+1,sum+num[depth]);
    dfs(depth+1,sum);
  }
}