[이코테] 만들 수 없는 금액

문제

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오

 

입력 조건

• 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. (1 <= N <= 1,000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 각 화폐 단위는 1,000,000 이하의 자연수이다.

 

출력 조건

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

# 입력 예시
5
3 2 1 1 9

# 출력 예시
8

 

 

풀이

핵심은 다음과 같다.

현재 동전 목록을 통해 {1, 2, 3, 4}라는 합을 만들 수 있다고 가정하자. 이 때 5는 만들 수 없기 때문에 Target이 된다.

만약 Target(5)보다 작거나 같은 값이 동전 그룹에 추가된다면, 기존 합집합에 해당 수를 더해 빈틈 없이 채울 수 있다.

하지만 6이 추가되면 전체 가능한 합 집합은 {1, 2, 3, 4, 6, 7, 8, 9, 10)이 된다. Target인 5가 채워지지 않으므로 5는 만들 수 없게 된다.

 

 

코드

n = int(input())
coin = list(map(int, input().split()))
coin.sort()

target = 1
for i in coin:
    if target < i:
        break
    target += i

print(target)

target을 1로 초기화하고 입력된 동전과 크기를 비교한다. 동전이 target보다 작거나 같은 경우에만 허용된다.

허용된 경우에는 target에 현재 for문을 돌고 있는 동전을 더해서 다음 타겟을 만든다. 

 

 

현재 동전을 target에 더하는 이유는?

예를 들어 target이 5라는 의미는 1~4까지는 만들 능력이 된다는 것이다. 현재 동전이 2라고 가정하면 이제 1~6까지 만들 능력이 되기 때문에 target을 7로 갱신하는 것이다.