11047 코인

11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

N,K = map(int, input().split())
temp = []
result = 0
for i in range(N):
    temp.append(int(input()))
for i in range(N - 1, -1, -1):
    if K // temp[i] >= 1:
        result += K // temp[i]
        K -= K // temp[i] * temp[i]
    elif K == 0:
        break
print(result)

그리디에 가장 대표적인 문제로 가장 적은 수로 거스름돈을 주는 방법을 찾는 문제이다

우선 이 문제에서는 가장 큰 동전부터 기존 값에서 빼나가면서 수를 더해야 한다.

이 때, range를 큰수에서 작은수로 가게 하고 싶을 때에는 range(N-1, -1, -1)형태로 사용해야하는데

만일 가운데 값을 0으로 지정하면 1까지만 참조하기 때문에 0 인덱스까지 참조하고 싶다면 -1이라고 써야 한다.