수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.
예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.
첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)
둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.
첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.
3
5 1 2
4
3
2 1 4
8
4
2 1 2 7
6
이 문제는 DFS 알고리즘을 이용한 조합을 사용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N;
static boolean[] nums;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
String[] input = br.readLine().split(" ");
int[] arr= new int[N];
int sum = 0;
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(input[i]);
sum += arr[i];
}
nums = new boolean[sum+2];
dfs(arr, 0, 0);
for(int i=1; i<nums.length;i++) {
if(!nums[i]) {
System.out.println(i);
break;
}
}
}
public static void dfs(int[] arr, int idx, int sum) {
if(idx>=1) {
nums[sum] = true;
}
if(idx==N) return;
for(int i=idx; i<N; i++) {
dfs(arr, i+1, sum+arr[i]);
}
}
}
안녕하세요 코드 짜신거 보고 궁금한점이 있어 댓글적습니다.
코드에 nums = new boolean[sum+2]; 에서 +2를 하신 이유를 알 수 있을까요?
만약에 +1로 할 경우에 테스트케이스 2번 (3 / 2 1 4 ) 이 공백으로 뜨더라구요
+2로 하면 정상 답(8)으로 출력되는데 이유가 뭔지 모르겠어서요..