이코테 - 만들 수 없는 금액(Python)

코딩테스트 문제를 풀다가 해설을 봐도 이해가 안 가서 정리하고자 글을 올립니다

 

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

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

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

 

 

A. 

1. 화폐 단위를 오름차순으로 정렬한 후, 생성한 target 변수와 크기를 비교한다
2. target 변수에 해당 화폐 단위를 더해주어 다음 target 값을 만든다
3. 각 단계에 target 값과 화폐 단위 값을 비교한다

 

Ex) 1, 1, 2, 3, 9 가 화폐 단위로 입력된 경우

 

1. target 값은 1부터 시작

target = 1, 처음 화폐 단위 1이므로 답이 될 수 없음. target + 1 하기

 

2. target = 2

화폐 단위 1이므로 < target. 답이 될 수 없음. target + 1 하기

 

3. target = 3

화폐 단위 2이므로 < target. 답이 될 수 없음. target + 2 하기

 

4. target = 5

화폐 단위 3이므로 < target. 답이 될 수 없음. target + 5 하기

 

4. target = 8

화폐 단위 이9므로 > target. target이 답이 됨 = 8

 

 

* 각 단계에 있어서 target 미만의 수를 앞의 화폐단위의 합으로 만들 수 있다는 것을 가정함. 실제로 구해보면 그렇다. 

 

 

 

코드 답안

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

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

print(target)