P.14225 부분수열의 합

14225 부분수열의 합

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	6931	3300	2237	43.966%

 

문제

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

 

예제 입력 1

 

3
5 1 2

예제 출력 1

 

 

4

예제 입력 2

 

3
2 1 4

예제 출력 2

 

 

8

예제 입력 3

 

4
2 1 2 7

예제 출력 3

 

6

코드

 

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

public class P_14225 {

    static int n;
    static int[] s;
    static boolean[] visited = new boolean[2000001];
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        subsequence(0, 0);

        for (int i = 1; i < visited.length; i++) {
            if (!visited[i]) {
                bw.write(Integer.toString(i));
                break;
            }
        }
        bw.flush();
    }

    public static void subsequence(int sum, int idx) {
        visited[sum] = true;
        if (idx == n) return ;

        subsequence(sum + s[idx], idx + 1);
        subsequence(sum, idx + 1);
    }
}

코드 설명

브루트 포스를 이용하면 되는 문제다.

 

먼저, 수열 s를 이용해서 구할 수 있는 값의 최댓값을 구한다.

수열 s의 크기는 최대가 20이며, s의 원소 각각의 최댓값은 100,000이다.

즉, 수열 s를 모두 더해서 구할 수 있는 수 중 가장 큰 값은 20 * 100,000 = 2000000이다.

 

수열 s의 부분수열의 합을 저장하는 배열로 visited를 두었는데 이 배열의 크기를 2000001로 설정한다.

1을 더한 이유는 0이 아닌 1부터 저장할 것이기 때문이다.

 

부분수열의 합을 구하는 과정은 subsequence라는 메소드를 이용했다.

이 메소드는 인자로 부분수열의 합을 의미하는 sum과 현재 수열 s에서 어느 부분을 가리키고 있는지 그 인덱스를 저장하는 idx를 인자로 갖는다.

 

수열 s의 각각의 원소는 더해지거나, 더해지지 않거나 둘 중 하나이다.

subsequence(sum + s[idx], idx + 1)은 idx에 있는 원소가 합에 더해졌다는 의미이고,

subsequence(sum, idx + 1)은 idx에 있는 원소가 합에 더해지지 않았다는 의미이다.

 

이렇게 재귀로 풀면 모든 경우의 수를 돌 수 있다.