백준_부분수열의 합_14225

// 알고리즘

 

1. 부분집합

 

2. check배열을 나올 수 있는 최대 수인 2000000 생성

 

3. 주어진 수의 부분집합을 구해 모두 더해서 check 배열에 표시

 

4. check배열을 1부터 시작하여 false인 값이 정답

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

public class 부분수열의합_14225 {

	static int N, arr[], ans;
	static boolean[] v;
	static boolean[] check;

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

		N = sc.nextInt();
		v = new boolean[N];
		check = new boolean[2000001];
		arr = new int[N];
		ans = 0;

		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}

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

	}

	private static void cal(int idx) {
		if (idx == N) {
			
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				if(v[i]) cnt+=arr[i];
			}
			
			check[cnt] = true;
			
			return;
		}

		v[idx] = true;
		cal(idx + 1);
		v[idx] = false;
		cal(idx + 1);

	}

}

※ n값이 20이라고 주어졌을 때, 부분집합의 개수가 2의 20승 이므로(백만)  부분집합으로 풀 수 있는 문제라고 생각

이후에는 그냥 쉽게 구현만 해서 정답이 나옴.