[BaekJoon] 백준 11047번 동전 0

[BaekJoon] 백준 11047번 동전 0

 

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

 

내코드

 

최소한의 동전으로 값을 표현해야한다.

그 순간 가장 최선의 선택인 특정 값보다 작은 값중 가장 큰 값을 선택해야 하므로 그리디 알고리즘이다.

 

# BaekJoon11047.py

n, k = map(int, input().split())
arr = []

for _ in range(n):
    arr.append(int(input()))
    
result = 0
arr.sort(reverse=True)
for i in arr:
    if k==0: break
    result += k // i
    k %= i
print(result)