[Baekjoon] 14225_부분수열의 합

Silver I

문제(출처: https://www.acmicpc.net/problem/14225)

---

< 부분수열의 합 >

 

문제 풀이 

 

모든 조합을 통해 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

 

 my solution (Java)

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

public class _14225_ { // 부분수열의 합
	static int arr[], answer[], n;
	static boolean result[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(bf.readLine());

		arr = new int[n];
		result = new boolean[2000001];

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			result[arr[i]] = true;
		}
		Arrays.sort(arr);

		for (int i = 2; i <= n; i++) {
			answer = new int[i];
			search(i, 0, 0);
		}

		for (int i = 1; i < result.length; i++) {
			if (!result[i]) {
				System.out.println(i);
				break;
			}
		}
	}

	private static void search(int max, int start, int idx) {
		if (idx == max) {
			int sum = 0;
			for (int i = 0; i < idx; i++) {
				sum += answer[i];
			}
			result[sum] = true;
			return;
		}
		for (int i = start; i < n; i++) {
			answer[idx] = arr[i];
			search(max, i + 1, idx + 1);
		}
	}
}

변수)
n : 수열의 크기
arr : 수열 S
result : 부분 수열의 합으로 나올 수 있는 자연수
answer : 부분 수열

 

수열의 크기를 입력받는다. 수열의 크기만큼 수열을 입력받는다. 입력받은 수열을 오름차순으로 정렬한 후 구할 수 있는 모든 조합을 구한다. 조합을 통해 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 찾아 출력한다.

 

search (조합 개수, 시작 인덱스, 인덱스 )

수열을 탐색하면서 조합을 구한다. 인덱스가 조합 개수와 일치하다면 조합을 다 구한 것이므로 현재 구한 부분 수열의 합을 구한다. 합을 구한 후 result 배열에서 그 값을 방문 처리한 후 종료한다.

---

---