[이것이 코딩테스트다] 만들 수 없는 금액

🗃️문제 설명

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 이하의 자연수입니다.

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

🖥️코드

import sys
input = sys.stdin.readline

N = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    if target < x:
        break
    target += x
print(target)

🧠아이디어

알고리즘 유형 : Greedy

동전 액면가를 더해가며 갱신하는데 이 때, 보유하고 있는 동전 액면가가 만들 수 있는 금액보다 크다면 만들 수 없는 금액이 된다.

쉽게 이해하기 위해 또 다른 테스트케이스를 만들었다.

TestCase#1. [3, 2, 1, 9]이라고 가정

1 + 2 + 3 = 6, 그리고 6 < 9이므로 만들 수 없는 최소 금액은 7이 된다는 것이다.

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 만들 수 없는 금액
모범 답안 - 만들 수 없는 금액