[백준/Python] 11047번. 동전 0

문제

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

 

 

 

풀이

전형적인 그리디 문제이다

목표 금액보다는 작은 동전중 가장 큰 숫자를 계속해서 취해 나가면 된다.

 

동전의 가치는 오름차순으로, 이전 숫자의 배수로 주어지기때문에 

3 900
300
800

이런 테스트 케이스와 같이 800을 먼저 취했더니 300을 취할 수 없는 상황같은건 고려하지 않아도 된다.

 

 

 

 

 

정답 코드

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

coins = [int(input()) for _ in range(N)]
coins.sort(reverse=True)

answer = 0
for coin in coins:
    while coin <= K:
        K-= coin
        answer += 1
print(answer)