백준 - 11047번: 동전 0 - 파이썬

백준 - 11047번: 동전 0 - 파이썬

문제

입출력 형식 및 출처

m,n = list(map(int, input().split()))
change_arr = []

for i in range(m):
    change = int(input())
    change_arr.append(change)

change_arr.reverse()

change_sum = 0
for change in change_arr:
    if n == 0:
        break
    if change > n:
        continue
    
    change_sum += n//change
    n %= change

print(change_sum)

그리디 알고리즘 문제

• 가장 큰 숫자의 거스름돈부터 나누어 차례로 몫을 더해준다
• 남은 돈을 좀 더 작은 숫자의 거스름돈으로 나누어 몫을 더해준다
• 2번의 과정을 반복한다