BOJ 11047번: 동전 0

www.acmicpc.net/problem/11047

11047번: 동전 0

아이디어:

값이 큰 동전을 최대한 많이 사용해야 사용하는 총 동전의 개수가 최소가 된다.

동전의 값은 오름차순으로 주어지므로, 주어진 동전 값을 순서대로 배열 arr에 넣고 인덱스 n-1부터 0까지 탐색하면서 k를 arr[i]로 나눈 몫을 더한다. 이때 k의 값은 k % arr[i]로 업데이트 하고 k % arr[i]가 0이되면 반복문을 탈출한다.

 

코드:

import sys
n, k = map(int, sys.stdin.readline().split())
arr = []
for _ in range(n):
    arr.append(int(sys.stdin.readline()))

ans = 0
for i in range(n-1, -1, -1):
    ans += k // arr[i]
    k = k % arr[i]
    if (k == 0):
        break
print(ans)