[BOJ] 11047 / 동전 0 / Python 파이썬

[BOJ] 11047 / 동전 0 / Python 파이썬

[BOJ] 11047 / 동전 0 / Python 파이썬

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

11047번: 동전 0

 

 

풀이

생각한대로 구현하니 풀어지는 간단한 그리디 알고리즘 문제이다.

 

주어진 금액에 가까운 가장 큰 동전의 개수부터 빼주면서 동전의 개수를 세어 주면 된다.

 

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

coins = []

for _ in range(N):
    coins.append(int(input()))

i = len(coins) - 1
res = 0
while K:
    if K < coins[i]:
        i -= 1
        continue
    res += K // coins[i]
    K = K % coins[i]

print(res)