공부 218일차: 백준 14225번 부분수열의 합 자바 java

14225 부분수열의 합

https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

 

 

 

---

백준 14225번 문제 부분수열의 합

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	9404	4456	3036	43.539%

문제

수열 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

힌트

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/323

공부 178일차: 백준 1182번 부분수열의 합 자바 java

이 문제와 유사하다

 

문제 조건에서 나올 수 있는 합의 최댓값인 2,000,000을 담을 수 있는 배열을 선언한다

int[] arr = new int[2_000_001]

 

저 문제의 코드에서 count를 구하는 식을 제외하여

static void DFS(int depth, int sum) {
  if(depth == n) {             
     return;
  }
  DFS(depth+1, sum+arr[depth]);
  DFS(depth+1, sum);
}

이 dfs 메서드로 모든 부분 수열의 합을 구한다

 

이때 arr[구해지는 부분 수열 합] 자리에 1씩 더한다

 

이후 dfs가 끝나면 모든 합을 구한 것이므로,

1부터 반복문을 돌려서 0인 숫자가 있으면 그것이 주어진 부분 수열로 구할 수 없는 가장 작은 자연수다

(카운팅 정렬과 방식이 유사하다고 보면 된다)

 

 

아래 정답코드의 주석에도 자세하게 적어보았다

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n, before;
    static int[] arr;
    static int[] answer = new int[2_000_001];
    // 숫자가 20이고 수열 s의 구성요소가 모두 최댓값 100,000 -> 합의 최댓값은 20 * 100,000
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        dfs(0,0);
        
        // 수열s는 자연수로만 이루어져 있으므로 합의 최솟값인 1부터 시작
        for(int i = 1; i < answer.length; i++) {
            if(answer[i] == 0) {                
                bw.write(i+"");
                break;
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
    
    static void dfs(int depth, int sum) {
        answer[sum]++;    // 합이 존재하면 그 자리에 숫자 넣기
        
        if(depth == n) {
            return;
        }
        
        // 트리 형식으로 모든 합을 확인한다고 보면 된다
        dfs(depth+1, sum+arr[depth]);
        dfs(depth+1, sum);
    }
 
}
 

 

 

 

---

다른 사람들 풀이를 보니 int[]가 아닌 boolean[]으로 해도 됐겠다