[Algorithm] 이코테 만들 수 없는 금액 | 파이썬 (그리디)

[문제]

동네 편의점의 주인인 동빈이는 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 이하의 자연수입니다.

 

[출력 조건]

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

[입력 예시]

5

3 2 1 1 9

[출력 예시]

8

 

문제 해결 TIP

일단 주어진 화폐 단위를 오름차순으로 정렬하고 1부터 차례대로 특정한 금액을 만들 수 있는지 확인해야 한다. 만들어야 하는 금액 변수를 target이라고 하자. 동전 종류가 1,1,2,3,9 인 경우 (1+1),2,3,9 일 때 괄호 속 합이 2이므로 다음 숫자 2와 같으므로 만들 수  있다고 본다. (1+1+2),3,9 일 때 역시 괄호 속의 합이 4이므로 다음 숫자 3보다 크므로 만들 수 있다. (1+1+2+3),9 일 때는 괄호 속의 합이 7이므로 다음 숫자 9보다 작다. 이는 9를 제외한 모든 작은 숫자들을 합쳐도 8을 만들 수 없다는 뜻이다. 따라서 target 변수에 오름차순으로 하나씩 수를 더해가며 다음 금액보다 작거나 같은 경우만 금액을 만들 수 있는 것이다. 

 

전체 코드

N = int(input())
money = list(map(int, input().split()))

money.sort()
target = 1
for i in money:
    if target<i:
        break
    target+=i
print(target)