[K 대회 기출] 만들 수 없는 금액

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

# 화폐 단위를 오름차순
coin.sort()

target = 1

for x in coin :
    if target < x :
        break
    target += x

print(target)

 

화폐를 오름차순으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 차례로 확인하면서

target 변수를 업데이트 하는 방법이다.

target 변수는 화폐들을 누적해서 더한 값이다. (target - 1 의 숫자까지 만들 수 있음을 보장!!)

즉, 화폐 단위들로 만들 수 있는 최대 금액을 갱신해 간다는 아이디어로 생각하면 된다.

 

이때, x가 target 보다 크다면, 두 화폐 사이에 만들지 못하는 수가 생긴다는 뜻이다.

왜냐면 target을 만드는 것이 목표인데, 이보다 더 큰 x가 주어진다면 당연히 만들 수 없음을 의미한다.

말로 적으니 다시 헷갈리는 듯 하여 예시를 들겠다.

 

예로 1 1 2 6 의 화폐가 주어졌다고 가정하자.

target은 1 -> 

1+1 (1까지 만들 수 있음을 확인함) -> 

1+1+1 (2까지 만들 수 있음을 확인함) -> 

1+1+1+2 (4까지 만들 수 있음을 확인함, 그러나 다음 화폐인 6은 5보다 크므로 target인 5를 만들 수 없음) 

 

에로 3 2 1 1 9 의 화폐가 주어졌다고 가정하자.

-> 1 1 2 3 9

target은 1 -> 1+1 -> 1+1+1 -> 1+1+1+2 -> 1+1+1+2+3 (못 만듦, 8 < 9 이므로)