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

 

주의할 점 : 수열 S를 이루고 있는 숫자가 100,000보다 작거나 같은 자연수, 수열의 크기는 최대 20 ==> 수열의 합으로 만들 수 있는 자연수를 기록하는 boolean 배열 sum의 크기 == 20 * 100,000 = 2000000

 

이것을 고려하지 않고 풀었다가 전체적인 로직은 맞게 구현 했으나 반례때문에 계속 틀렸다..

ㅎㅎ

 

 

문제 풀이

 

모든 경우의 수를 구하면서 문제를 풀어야 하기 때문에 dfs를 구현해서 합으로 만들 수 있는 숫자를 기록했다.

static void dfs(int start, int value){
    if(start>=N){
        return;
    }
    for(int i=start; i<N; i++){
        if(!visit[i]) {
            visit[i]=true;
            value=value+arr[i];
            if(value<=2000000) {
                sum[value] = true;
            }
            dfs(i+1,value);
            value-=arr[i];
            visit[i]=false;
        }
    }
}

 

여기서 visit[i]를 다시 false로 바꾸고 value에서 다시 arr[i]를 빼줘야지 수열의 숫자를 더하지 않은 경우도 구할 수 있다.

 

<전체 코드>

import java.util.Arrays;
import java.util.Scanner;

public class Problem14225 {
    static int[] arr;
    static int N;
    static boolean[] visit;
    static boolean[] sum=new boolean[2000001];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N=scanner.nextInt();
        arr=new int[N];
        visit=new boolean[N];

        for(int i=0; i<N; i++){
            arr[i]=scanner.nextInt();
        }
        Arrays.fill(visit,false);
        Arrays.fill(sum,false);

        dfs(0,0);

        int count = 1;
        while(true){
            if(count>2000001){
                break;
            }
            if(!sum[count]){
                System.out.println(count);
                break;
            }
            else{
                count++;
            }
        }


    }
    static void dfs(int start, int value){
        if(start>=N){
            return;
        }
        for(int i=start; i<N; i++){
            if(!visit[i]) {
                visit[i]=true;
                value=value+arr[i];
                if(value<=2000000) {
                    sum[value] = true;
                }
                dfs(i+1,value);
                value-=arr[i];
                visit[i]=false;
            }
        }
    }
}