만들 수 없는 금액 코드 및 해설 (파이썬)

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 4, p 314

 

먼저 주어진 동전으로 만들 수 있는 모든 금액을 구한 후, 이중 불연속인 구간을 찾아 만들 수 없는 금액의 최솟값을 구합니다.
만들 수 있는 모든 금액을 구할 때는 possible_amount라는 함수를 만들어 사용했습니다. 오름차순으로 정렬된 동전의 리스트가 입력으로 주어지면, 첫 번째 두 개의 동전과 그 두 개의 동전의 합으로 이루어진 집합을 만듭니다. 이후 세 번째 동전부터 모든 동전을 하나씩 살피면서 지금까지 만들어진 집합 amounts의 모든 값에 현재 동전의 값을 더한 값을 집합에 추가합니다. 이후 amounts 집합을 리스트로 변환해 반환합니다.
이렇게 얻은 만들 수 있는 모든 금액 중에서 1이 없으면 정답으로 1을 반환합니다. 1이 있다면 숫자의 연속성이 끊기는 구간을 찾아 그 구간의 마지막 숫자에 1을 더한 값을 최종 정답으로 반환합니다.

 

import sys

N = sys.stdin.readline()
coins = list(map(int, sys.stdin.readline().split()))
coins.sort()

# 주어진 동전으로 만들 수 있는 모든 금액을 구함
def possible_amount(coins):
    first2 = coins[:2]
    # 가장 금액이 작은 두 동전으로 이루어진 집합
    amounts = set(first2)
    # 가장 금액이 작은 두 동전의 합
    amounts.add(sum(first2))
    # 세 번째 동전부터 하나씩 꺼내면서, 각 amount 값에 동전 금액 만큼 더함
    for i in range(len(coins[2:])):
        amounts |= set([a + coins[i+2] for a in amounts])
    return list(amounts)

possibles = possible_amount(coins)

# 가장 작은 만들 수 있는 금액
prev = possibles.pop(0)
# 1이 아니면 1원을 만들 수 없는 거니까 1을 프린트
if prev != 1:
    print(1)
else:
    for p in possibles:
        # 연속된 숫자가 아니면 
        if prev + 1 != p:
            print(prev+1)
            break
        else:
            prev += 1