[Java] 14225 부분수열의 합

문제

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

문제 풀이

숫자의 범위는 10만이고 갯수는 최대 20개이다. 즉 발생할 수 있는 합은 20 * 100000 이다.

해당 크기 + 1 만큼의 boolean 배열을 만들고 입력받은 수 를 더해서 만들 수 있는 숫자를 구한다.(중복 값 사용x)

해당 숫자의 인덱스 위치에 값을 true로 바꿔준다.

이후 반복문으로 첫 false 값을 가지고 있는 배열의 인덱스 값을 출력해주면 된다.

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class SumOfSubsequences {
    private static int N;
    private static int[] S;
    private static boolean[] check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        S = new int[N];
        check = new boolean[20 * 100000 + 1];

        String[] s = br.readLine().split(" ");
        for(int i = 0; i < N; i++){
            S[i] = Integer.parseInt(s[i]);
        }

        dfs(0 , 0);

        for(int i = 1; i < check.length; i++) {
            if (!check[i]) {
                System.out.println(i);
                break;
            }
        }
    }

    private static void dfs(int depth, int num){
        if(depth == N) {
            check[num] = true;
            return;
        }

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

 

시간초과 1

제시 받은 이 숫자들을 이용해 만들 수 있는 모든 수를 dfs로 찾은 후 list에 담고 이후 1부터 list에 있는지 확인하여 없으면 출력하고 종료하는 코드

방문체크를 통해서 중복 값도 이용해서 만들 수 없게하고 모든 수를 찾고 list에 중복값도 체크하는 등 시간을 많이 소요하여 시간초과로 실패

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class SumOfSubsequences {
    private static int N;
    private static int[] S;
    private static boolean[] check;

    private static final List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        S = new int[N];
        check = new boolean[N];

        String[] s = br.readLine().split(" ");
        for(int i = 0; i < N; i++){
            S[i] = Integer.parseInt(s[i]);
        }

        Arrays.sort(S);

        dfs(0 , 0);

        int i = 1;
        while(true){
            if(!list.contains(i)) {
                System.out.println(i);
                break;
            }
            i++;
        }
    }

    private static void dfs(int depth, int num){
        if(!list.contains(num)){
            list.add(num);
        }

        if(depth == N)
            return;

        for(int i = 0; i < N; i++) {
            if(!check[i]) {
                check[i] = true;
                dfs(depth + 1, num + S[i]);
                check[i] = false;
            }
        }
    }
}