만들 수 없는 금액 - 그리디

지니고 있는 동전들로 만들 수 없는 target 값을 찾아야 하는데, 바꿔말하면 지니고 있는 동전들로 target-1까지의 모든 금액을 만드는 방법을 찾아야 한다.

따라서 금액이 최소인 동전부터 하나씩 조합해보면서 만들 수 있는 target-1값을 갱신하겠다는 아이디어가 핵심이 되겠다. 

 

위 예시와 같이 현재 동전이 1,1,2,3,9원이 있다고 하자. 1원 하나로 만들 수 있는 금액은 다음과 같을 것이다.

• 1 = 1

 1원까지는 1원 하나로 전부 만들 수 있으니, 또 1원을 추가하여 [1,1]원으로 만들 수 있는 금액은 다음과 같을 것이다.

• 1 = 1
• 1 + 1 = 2

 2원 까지는 [1,1]원으로 전부 만들어 볼 수 있으니, 2원을 추가하면 경우의 수는 다음과 같을 것이다.

• 1 = 1
• 2 = 2
• 1 + 2 = 3
• 1 + 1 + 2 = 4

 4원 까지는 [1,1,2]원으로 전부 만들어 볼 수 있으니, 3원을 추가하면 6원까지 전부 만들어 볼 수 있을 것이다. 하지만 여기에 9원이 추가된다면, 6원 까지는 전부 만들어 볼 수 있으나 9보다 작은 금액, 즉 7,8원은 가지고 있는 동전으로 만들어 볼 수 없을 것이다. 따라서 이때 답은 7원이 될 것이다. 이와 같은 로직으로 문제 풀이가 가능하다. 기존에 있던 동전들에 새로 동전을 가져와 섞어줬을 때, 가지고 있는 동전들로 1원 부터 (traget-1)원 까지 전부 만들어볼 수 있다는게 전제된다면 다음에 섞어주는 동전 x원이 target 보다 컸을 때 target, target+1, ..., target+x-1원은 조합 불가능한 액수가 될 것이다. 예시처럼, 6원까지는 만들어볼 수 있을 때 새로 섞어주는게 5원이라면 어차피 기존의 동전으로 6원까지는 조합이 가능하니 새로 11원까지 조합이 가능해지겠지만, 만약 새로 섞어주는게 9원이라면 7원, 8원은 만들 수 없는 액수가 되는 것이다.

코드

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)