[Baekjoon 11047 / python / 실버4] 동전 0

N, money = map(int, input().split())  # 동전 종류, 돈

coinBox = []

for _ in range(N):

    coinBox.append(int(input()))

coinBox.reverse()

cnt = 0

for coin in coinBox:  # 큰 동전부터 차례로 대입된다

    if money >= coin:

        cnt += money // coin

        money = money % coin

print(cnt)

 

그리디 알고리즘으로 해결할 수 있는 문제이다.

 

매 순간 최적의 선택을 하면 되기 때문에, 구현이 그리 어렵진 않다.

동전을 입력받은 후, 반복문을 돌리면 큰 동전부터 나오도록 reverse()메소드로 뒤집는다.

 

이후 큰 동전부터 반복문을 돌며, 남은 돈이 동전 가치보다 같거나 크다면 나눈다.

나눈 몫은 동전의 개수로 추가하고, 나눈 나머지는 다음 계산에 사용하면 된다.