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

 

www.acmicpc.net/problem/14225

14225번: 부분수열의 합

풀이

1. set을 이용해 부분집합의 합 구하기

 

set은 중복된 값이 들어가지 않으므로 부분집합의 합을 구할 때 마다 set에 결과를 저장했다.

근데 굳이 set에 결과를 넣지 않고 2번째 풀이와 같이 index를 부분집합의 합으로 갖는 배열에다가 저장해도 될 듯하다.

(시간이 너무 오래 걸린다!)

public class BOJ_14225 {
	static int S;
	static int[] arr;
	static Set<Integer> sums = new HashSet<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		S = Integer.parseInt(in.readLine());
		arr = new int[S];
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		for(int i=0;i<S;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		subset(0,new boolean[S]);
		int start = 1;
		boolean canFind = true;
		while(canFind) {
			if(sums.contains(start)) {
				canFind = true;
				start++;
			}else {
				canFind = false;
				break;
			}
		}
		System.out.println(start);
		
	}
	static void subset(int cnt, boolean[] visited) {
		if(cnt == S) {
			int sum = 0;
			for(int i=0;i<S;i++) {
				if(visited[i]) {
					sum += arr[i];
				}
			}
			sums.add(sum);
			return;
		}
		visited[cnt] = false;
		subset(cnt+1, visited);
		visited[cnt] = true;
		subset(cnt+1, visited);
	}
	
	
}

2. dfs

 배열을 이용하자!

public class BOJ_14225_2 {
	static int S;
	static int[] arr;
	static boolean[] nums;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		S = Integer.parseInt(in.readLine());
		arr = new int[S];
		int sum = 0;	// 최대값
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		for(int i=0;i<S;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			sum += arr[i];
		}
		
		nums = new boolean[sum+2];
		
		dfs(0,0);
		
		for(int i=1;i<nums.length;i++) {
			if(!nums[i]) {
				System.out.println(i);
				return;
			}
		}
	}
	static void dfs(int cnt, int sum) {
		if(cnt >= 1) {
			nums[sum] = true;
		}
		if(cnt == S) return;
		for(int i = cnt;i<S;i++) {
			dfs(i+1, sum+arr[i]);
		}
	}
	
}

결과

 

dfs로 풀었을 때 10배 더 빠르다