[백준/자바] 14225 부분수열의 합

문제 링크

---

문제

수열 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

3
5 1 2

예제 출력 1

4

예제 입력 2

3
2 1 4

예제 출력 2

8

예제 입력 3

4
2 1 2 7

예제 출력 3

6

---

설명

N의 크기는 1 이상 20 이하의 수이기 때문에 조합으로 구하지 않는다.

 

예제가 다음과 같을때,

4

2 1 3 7

 

2^(N-1) 이상 2^N미만의 수를 2진수로 변환하며 4글자인 비트 마스크를 구할 수 있다.

여기서 N = 4이기 때문에 8 이상 16 미만의 수를 탐색한다.

(2^N미만인 이유는 2^N은 N+1 자리기 때문이다.)

	2진수	2진수 반전	1 인덱스 합	0 인덱스 합
8	1000	0001	2	1 + 3 + 7
9	1001	0110	2 + 7	1 + 3
10	1010	0101	2 + 3	1 + 7
11	1011	0100	2 + 3 + 7	1
12	1100	0011	2 + 1	3 + 7
13	1101	0010	2 + 1 + 7	3
14	1110	0001	2 + 1 + 3	7
15	1111	0000	2 + 1 + 3 + 7

2진수에서 1인 인덱스의 합과 0인 인덱스의 합을 이용해 나올 수 있는 모든 조합을 탐색할 수 있다.

나올 수 있는 수는 중복이 발생할 수 있기 때문에 중복제거를 위해 HashSet을 사용한다.

코드