백준 11047 - 동전 0

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

11047번: 동전 0

N, K = map(int, input().split())
arr = []
for i in range(N):
    arr.append(int(input()))

count = 0
for money in arr[::-1]:
    if K==0:
        break
    if K//money > 0:
        count+=K//money
        K = K%money
print(count)

그리디 알고리즘 문제다. 

 

내가 가진 돈의 단위들 중 큰 것부터 차례대로 입력받을 K값과 비교해서, 내 돈으로 K값을 나눌 수 있는 범위부터 순차적으로 연산을 수행한다.

이를 테면 

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

의 연산이 있다고 할 때,

4200원은 50000원,10000원,5000원으로는 표현할 수 없으므로 이것들은 그냥 지나가면 되고

1000원인 경우 4200원 중 4000원을 표현할 수 있으므로 4200//1000인 4를 count에 집어넣은 뒤

표현하지 못하는 200원만 K값에 남겨서 다시 반복문 연산을 수행한다.

이후 500원으로는 200원을 표현할 수 없으므로 다시 지나가게 되고

100원인 경우 200원 모두를 표현할 수 있으므로 200//100인 2을 count에 집어넣는다.

 

각 연산이 끝날 때마다 K값이 0인 경우는 break해서 n//0 과 같은 ZeroDivisionError를 발생시키지 않도록 한다.

 

이후 count 값을 출력한다.

 

실버 4 달성!