백준 11047: 동전 0 (Python)

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

11047번: 동전 0

 

n, k = map(int, input().split())
a = []
cnt = 0

for i in range(n):
    a.insert(0, int(input()))

for i in a:
    cnt += k // i
    k %= i
    if k == 0:
        break

print(cnt)

 

1. 나눌 수 있는 가장 높은 숫자로 나눔 -> cnt

2. 나머지 -> 나눌 수 있는 가장 높은 숫자로 나눔 -> cnt

3. 반복

 

위의 알고리즘을 수행하기 위해 입력되는 가치들을 내림차순으로 정렬하였다.

(가치는 처음부터 오름차순으로 입력되기 때문에 입력 받는 순으로 리스트의 맨 앞 인덱스에 추가시킴)

그 후 리스트 안을 돌면서 1~2 과정 수행하고 k=0이 됐을 때 반복을 중단하였다.