백준 / 동전 0 / 11047

Question

문제링크
Silver 3

Logic

기본 구조 : greedy
1. 입력된 동전들을 오름차순으로 정렬해 저장한다.
2. pop 함수로 하나씩 빼서, K와 대조한다.
3. K가 target 이상이라면, 가능한 만큼 해당 동전을 계산하고 K에서 제한다.
4. 잔액이 0이 되거나, 동전이 떨어지면 계산을 종료한다.

Code

from sys import stdin

N,K = map(int,stdin.readline().rstrip().split())
coins = sorted([int(stdin.readline().rstrip()) for _ in range(N)])
cnt = 0
while(K>0):
    if not coins:
        break
    target = coins.pop()
    if K>=target:
        nn = K//target
        K-=nn*target
        cnt+=nn

print(cnt)