14225 부분수열의 합 (나올 수 없는 가장 작은 수)

https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

 

부분수열의 합 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

1482

743

516

47.645%

문제

수열 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의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

 

 

<풀이>

1. 경우의 수 공집합 제외하면 2^N-1개 많지않음.

 

2. 재귀를 이용해서 전부 부분집합을 만들어서 나오는 수들의 인덱스를 저장

 

3. 인덱스가 저장된 리스트의 값들을 체크하며, 체크되지 않는 수들중 가장 작은값 출력.

 

#include<iostream>
using namespace std;

void go(int index, int sum);

bool check[2000001];
int arr[20];
int N;

int main(void)
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
	}
	go(0, 0);

	for (int i = 0; i < 2000000; ++i)
	{
		if (!check[i])
		{
			cout << i << '\n';
			return 0;
		}
	}
	return 0;
}
void go(int index, int sum)
{
	if (index == N)
	{
		check[sum] = true;
		return;
	}

	go(index + 1, sum + arr[index]);
	go(index + 1, sum);
}