[코테] 백준 재귀 14225번 문제

14225번 : 부분수열의 합

문제 링크

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

문제풀이

수열을 오름차순으로 정렬한 이후, 3개 원소를 가진 배열을 예로 들어 000 ~ 111까지 원소의 합을 저장하고 1부터 문제에서 주어진 최대수인 99999 * 20만큼 순회하며 해당 숫자를 표현할 수 있는 지 검사한다.

import sys
input = sys.stdin.readline

N = int(input())
arr = sorted(list(map(int, input().split())))

# 모든 원소의 부분수열 합을 리스트에 저장
sumList = []
for i in range(1, (1 << len(arr))+1) :
    num = 0
    for j in range(len(arr)-1, -1, -1) : 
        if i == 0 :
            break
        if i >= 2 ** j :
            i -= 2 ** j
            num += arr[j]
    sumList.append(num)

# 1부터 최대수까지 순회하며 해당 수가 합 리스트에 없으면 출력 및 반복문 나가기
sumList = set(sumList)
for num in range(1, 99999 * 20 + 1) :
    if num not in sumList :
        print(num)
        break