[Python] 백준 11047 동전 0

 

문제 분석

• n 종류의 동전
• 각 종류는 모자르지 않을만큼 많다.
• 동전의 합을 k로 만드는 최소 동전 수 구하기

 

코드 설계

• 동전의 가치를 큰 순서대로 비교
• 동전의 가치를 list로 저장 - 내림차순 정렬
• 큰 수부터 k와 비교하면서 
• 만약 k > coin[ i ] 이면
• 동전개수 += k // coin [ i ] 하고 아니면 다음 반복문으로 넘어가기
• 다음 반복문에 k % coin[ i ] 넘겨주기
• 만약 k == 0 이 되면 동전 개수 return

 

정답 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
sum = 0
coins = []

for i in range(n) :
    coins.append(int(input()))

coins.sort(reverse=True)

cnt = 0
remain = 0

for c in coins :
    if k == 0 :
        break
    if k >= c :
        cnt += k // c
        k = k % c
    # else :
    #     continue

print(cnt)