[백준] 11047 : 동전 0 - Python

그리디 알고리즘

문제해결
결국 가장 큰 값의 동전은 작은 값들의 동전들의 배수이므로 그리디 알고리즘으로 해결 가능해짐.

소스코드

import sys

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

data = []
for i in range(N):
    data.append(int(input()))

data.sort(reverse = True)
cnt = 0
for i in range(N):
    if data[i] > K:
        continue
    cnt += K // data[i]
    K = K % data[i]

    if K == 0:
        break

print(cnt)