[코테 스터디] 그리디, 만들 수 없는 금액

Q04. 만들 수 없는 금액

🐣문제

주어진 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

🐥풀이

동전의 종류가 주어졌을 때, 오름차순으로 x번째 동전을 체크하는 케이스를 생각해보자. 첫번째 동전부터 (x-1)번째 동전까지의 합을 SUM(x-1)이라고 하자. 또한, (x-1)개의 동전으로 1부터 SUM(x-1)까지의 금액을 만들 수 있다.


1. SUM(x-1)+1 >= (x번째 동전의 값)
1부터 SUM(x-1)까지는 (x-1)개의 동전으로도 만들 수 있다. 즉, x번째 동전을 추가하여, 1+SUM(x-1)부터 (x번째 동전의 값)+SUM(x-1) 금액까지도 만들 수 있다. 따라서 1부터 SUM(x) 금액까지 만들 수 있게 된다.


2. SUM(x-1)+1 < (x번째 동전의 값)
(x-1)개의 동전으로 만들 수 있는 금액과 x번째 동전의 값 사이에 공백이 생긴다. 즉, SUM(x-1)+1의 값은 (x-1)개의 동전으로도, x번째 동전으로도 만들 수 없으므로 SUM(x-1)+1이 만들 수 없는 최소 금액이 된다.

• SUM(x-1)+1까지 판단하는 이유.
  

🐓코드

n = int(input())
coins = sorted(list(map(int, input().split())))

result = 1
for coin in coins:
  if result < coin: # 2번 케이스
    break
  result += coin # 1~result까지 모두 만들 수 있는 금액

print(result)

⭐2022.03.28

제대로 이해하지 못하고 넘어갔던 문제여서 다시 문제를 읽고 코드를 이해하는 것에 시간이 꽤나 걸렸다 ㅠㅅㅠ 'SUM(x-1)+1까지 판단하는 이유'를 따로 적어놓은 것은 내가 이 지점에서부터 이해를 못했기 때문에 ㅋㅋ..