[파이썬, Python] 백준 11047: 동전 0

문제

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

11047번: 동전 0

코드

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
coin = []
ans = 0

for _ in range(n):
    coin.append(int(input()))

coin.sort(reverse = True)

for i in coin:
    if k >= i:
        ans += k//i
        k %= i
        if k <= 0:
            break
print(ans)

설명

그리디 알고리즘을 활용하여 푸는 문제이다.
이는 현재의 선택이 각 단계에서 가장 최선이 되는 알고리즘이다.

동전의 개수를 최소로 갖기 위해서는 높은 가격의 동전이 많을수록 유리하다.

이를 활용하여 동전을 역순으로 정렬해 준다.
이후 각 동전이 목표액보다 작다면 목표액에서 동전을 나눈 몫을 정답에 더해주고,
나머지를 목표액으로 다시 설정해 준다.

k가 0이 되면 반복문을 종료하고 정답을 출력한다.