만들 수 없는 금액

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

예를 들어, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐단위)동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원 입니다.

또 다른 예시로, N = 3이고 각 동전이 각각 3원, 5원, 7원짜리 (화폐 단위) 동전이라고 가정합니다. 이떄 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값을 1원 입니다.

ex)
5
3 2 1 1 9

8

3
3 5 7

1

from itertools import combinations

n = int(input())
arr = list(map(int, input().split()))

if n == 1:
    if arr[0] == 1:
        print(2) 
    else: print(1) 
else:
    temp_set = set(arr)
    temp_set.add(sum(arr))
    for i in range(2, len(arr)):    
        for j in list(combinations(arr, i)):
            temp_set.add(sum(j))
    temp_set = list(temp_set)
    for i in range(1, len(temp_set)):
        if i not in temp_set:
            print(i)
            break

해설

나는 동전으로 만들 수 있는 모든 경우의 조합을 만들어 보고
1부터 조합의 값까지 증가시키면서 안에 있는지 없는지 확인하는 방식으로 구현했습니다.

우선 범위가 1일 경우 1아니면 2이라 못박았고

다음부터 itertools의 combination을 통해 주어진 배열로 부터 만들 수 있는 모든 경우의 수를 temp_set에 담았다.
그리고 1부터 증가시키면서 해당하지 않은 수를 발견할 경우 print하고 종료했다.

느낀점

우선 내 풀이가 맞는 풀이인지 모르겠다.
내 생각에 시간복잡도를 고려하지 않는다면, 틀린 답처럼 보이진 않는다.
그리고 여기에 입력 값의 범위가 1<= N <= 1,000 이기 때문에 시간복잡도도 안정적이지 않을까 싶다.