[PY] 11047 : 동전 0

https://www.acmicpc.net/problem/11047

그리디 알고리즘을 사용하는 아주 간단한 문제이다.

아이디어는 이렇게 구상한다.

1. 입력으로 동전 갯수, 필요한 요구 금액, 동전 종류를 입력받는다.
2. 동전 종류는 내림차순으로 정렬한다. 큰 수부터 대 봐야 하기 때문이다.
3. 동전이 빠져도 유효한 상황인 경우에만 동전의 금액을 필요한 요구 금액에서 뺀다.
   1. 여기서 유효한 상황은, 동전이 빠졌을 때도 잔액이 0 이상이여야한다.
4. 끝!

import sys
input = sys.stdin.readline

coinCnt, req = map(int, input().split())
coinList = [0] * coinCnt
resultCnt = 0

for i in range(coinCnt):
    insertCoin = int(input())
    coinList[i] = insertCoin

coinList.sort(reverse=True)

for coin in coinList:
    while req >= coin:
        resultCnt += req // coin
        req %= coin
        


print(resultCnt)

사실 단순히 coin(값)만큼 빼면 된다고 생각했는데,

나머지 연산과 몫으로 인한 동전 갯수를 구할 수 있다는 부분에서 놓침이 있었음을 반성하기로 했다.