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

부분수열의 합

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

4358

2167

1462

46.149%

문제

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

 

 

문제 풀이

 

첫번째 예시 문제를 풀어보자.

아래 예시 문제는 동전 뒤집기를 했을 때 나올 수 있는 경우의 수를 구하는 것과 유사한 방식으로 해결할 수 있다.

3
5 1 2

모든 자리의 값을 사용할 수도, 안 하수도 있는 2가지의 경우가 있다.

첫 번째 index 자리의 값을 사용하는 경우 (5)

첫 번째 index 자리의 값을 사용하지 않는 경우 (0)

 

첫 번째 index 자리의 값을 사용하였고, 두 번째 index 자리의 값을 사용하는 경우 (5+1)

첫 번째 index 자리의 값을 사용하였고, 두 번째 index 자리의 값을 사용하지 않는 경우 (5)

첫 번째 index 자리의 값을 사용하지 않았고, 두 번째 index 자리의 값을 사용하는 경우 (1)

첫 번째 index 자리의 값을 사용하지 않았고, 두 번째 index 자리의 값을 사용하지 않는 경우 (0)

 

세 번째 index 자리의 값도 위와 같은 case로 진행하면 된다.

static void dfs(int index, int currTotal) {

  dfs(index + 1, currTotal + info[index]);
  dfs(index + 1, currTotal);
}

모든 index를 다 확인 하였다면 

중복된 값은 필요가 없기 때문에 결과값을 set에 저장한다.

static void dfs(int index, int currTotal) {
  if (index == n) {
      set.add(currTotal);
      return;
  }
}

오름차순으로 결과 값을 정리한다.

List<Integer> resAry = new ArrayList<>(set);
Collections.sort(resAry);

결과 값을 차례대로 살펴보면서, 중간에 빈 값이 있으면 출력을 하면서 for문을 멈추고

빈 값이 없으면 계속해서 다음 값을 살펴본다.

int res = 1;
boolean isTrue = false;
for (int i = 1; i < resAry.size(); i++) {
    if (res != resAry.get(i)) {
        isTrue = true;
        break;
    }
    if (res == resAry.get(i)) {
        res++;
        continue;
    }
}
System.out.println(res);

모든 코드는 아래와 같다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class baekjoon14225 {
    static HashSet<Integer> set = new HashSet<>();
    static int n;
    static int[] info;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        info = new int[n];
        for (int i = 0; i < n; i++) {
            info[i] = sc.nextInt();
        }
        dfs(0, 0);
        List<Integer> resAry = new ArrayList<>(set);
        Collections.sort(resAry);

        int res = 1;
        boolean isTrue = false;
        for (int i = 1; i < resAry.size(); i++) {
            if (res != resAry.get(i)) {
                isTrue = true;
                break;
            }
            if (res == resAry.get(i)) {
                res++;
                continue;
            }
        }
        System.out.println(res);

    }

    static void dfs(int index, int currTotal) {
        if (index == n) {
            set.add(currTotal);
            return;
        }

        dfs(index + 1, currTotal + info[index]);
        dfs(index + 1, currTotal);
    }
}