[백준] G5 14225 부분수열의 합 (java)

www.acmicpc.net/problem/14225

14225번: 부분수열의 합

 

풀이

 

1) 부분집합을 구함

2) check[부분집합의 합] = true

3) 부르는 값이 true 인지 확인

 

주의사항

 

1) S의 원소의 최댓값이 100000이고 N의 최댓값이 20이므로 100000 * 20 만큼의 공간이 필요하다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_G5_14225_부분수열의합 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,S[];
	static boolean isSelected[], check[] = new boolean[2000001];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		S = new int[N];
		isSelected = new boolean[N];
		tokens = new StringTokenizer(input.readLine());
		for(int n=0; n<N; n++) {
			S[n] = Integer.parseInt(tokens.nextToken());
		}
		subSet(0);
		
		for(int i=1; i<check.length; i++) {
			if(!check[i]) {
				System.out.println(i);
				break;
			}
		}
	}

	private static void subSet(int cnt) {
		if(cnt == N) {
			int sum = 0;
			for(int i=0; i<N; i++) {
				if(isSelected[i]) {
					sum += S[i];
				}
			}
			check[sum] = true;
			return;
		}
		isSelected[cnt] = true;
		subSet(cnt+1);
		isSelected[cnt] = false;
		subSet(cnt+1);
	}

	static String src =
			"4\r\n" + 
			"2 1 2 7";
}

 

 

후기

 

다른 사람들의 코드와 비교하면 조금 느린데 이유는 내가 알고있는 부분집합은 isSelected[]라는 boolean형 배열을 이용하는 방식이라서 절차가 2번이지만 다른사람의 코드는 애초에  파라미터를 2개를 주어서 dfs를 돌렸다.

이것도 고쳐야하나? 그냥 익숙한거 써야지 해서 걍 내비뒀다.

부분집합은 잘 안나와서 잊고있었는데 오늘 다시한번 상기시킬수 있어서 좋았다.