문제

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

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

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

  • 입력조건

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 N 1,000)

둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.

  • 출력조건

첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

최종 코드

만들 수 없는 정수 금액을 구하려면 결국 모든 조합을 봐야하지 않을까? 생각해서 combinations 메소드로 가능한 합을 모두 구해서 최솟값을 구했는데, 이렇게하면 아마 시간이 초과될 것이다. (테스트해볼 곳이 없어서 확실한지는 모르겠음)

그래서 답을 찾아본 결과 동전을 오름차순으로 정렬하고 계속해서 더한다. 만약 지금까지 더한 값 + 1이 다음 동전의 값보다 작으면 지금까지 더한 값 + 1이 만들 수 없는 최솟값이 된다.

예를 들어 동전이 [1, 1, 2, 3, 9]라면 누적합은 [1, 2, 4, 7, 9]이다. 여기서 7 + 1 < 9 이므로 8이 만들 수 없는 최솟값이 되는 것이다.

import sys

n = int(sys.stdin.readline().strip())
coins = sorted(list(map(int, sys.stdin.readline().split())))
cnt = 1

for coin in coins:
    if cnt < coin:
        print(cnt)
        break
    cnt += coin

참고 사이트