[ 완전탐색] 14225번 부분수열의 합

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

14225번: 부분수열의 합

 

---

 

문제

 

---

해결 과정

 

저퀄리티 그림

예제 입력 1번 경우의 그림이다.

아무 것도 없는 상태에서 각 배열의 값을 DFS 방식으로 탐색하며 

store라는 배열에 각 수열의 합을 채워 넣는 방식이다.

이때, store 배열은 조건에 "100,00보다 작거나 같은 수" 가 최대 20개까지 주어지니까 1~2,000,000 으로 범위를 생각하여

store의 배열 크기를 2,000,001로 설정하였다.

 

---

코드

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

class Main {
    private static int N; // 수열의 크기
    private static int[] S;
    private static int[] store = new int[2000001]; // 100,000 이 20번 나올거 고려하여 1~2,000,000


    private static void DFS(int depth, int sum) {
        if(sum!= 0) store[sum] = sum;
        if(depth == N) return;
        int new_sum = (sum + S[depth]);
        DFS(depth + 1, new_sum);
        DFS(depth + 1, sum);
    }


    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];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            S[i] = Integer.parseInt(st.nextToken());
        }
        DFS(0,0);
        int answer = 0;
        for (int i = 1; i <= store.length; i++) {
            if(store[i] == 0) {
                answer = i;
                break;
            }
        }
        System.out.println(answer);
    }
}



/*

0,0 으로 DFS 쭉 돌려
그 합친 결과를 store 배열에 넣고
1부터 찾아 없으면 return

 */