[백준] 11047번 동전 0 (Python)

문제

 

www.acmicpc.net/problem/11047

11047번: 동전 0

 

코드

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

d = [int(input()) for _ in range(N)]

d.sort(reverse=True)

result = 0
for i in range(N):
    if d[i] > K:
        continue
    else:
        result += K // d[i]
        K = K % d[i]
print(result)

 

코드설명

그리디 알고리즘 문제로 눈앞에 최적의 해만 선택해도 최적의 해를 얻을 수 있다.

 

최적의 해를 선택할 수 있도록 정렬을 거꾸로 만들어주고 K의 값보다 나눠야 하는 값이 크다면 다음으로 넘어간다.

K와 같거나 작은 수중에 가장 큰수로 나눠주고 K값을 갱신해준다음 for문이 끝날때 까지 돌면된다.