[백준/파이썬] 11047번: 동전 0

문제

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

풀이

• n종류의 동전
• 각 종류의 동전은 매우 많이 있음
• 이 동전들을 가지고 k원을 만들어야 함
• 최소의 동전 개수를 사용

예제 입력

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

10종류의 동전(1원, 5원, 10원, ...)을 가지고 4200원을 만들어야 합니다.
4200원을 만들기 위한 최적의 방법은 1000원짜리 4장, 100원짜리 2개를 이용하는 것입니다.

이렇게 최적의 동전 개수를 구하기 위해선 가장 큰 동전 단위부터 계산하면 됩니다.

입력 조건을 보면 동전의 종류는 오름차순으로 입력되기 때문에 입력된 값을 뒤집어주어 이를 반복문을 통해 계산하면 됩니다.

coin = [int(input()) for _ in range(n)]
coin.reverse()

이제 돈 계산을 위한 반복문을 선언해주면 됩니다.

for i in coin:
    if k // i > 0:
        cnt += k // i
        k %= i

입력된 동전의 종류를 역순으로 탐색하여 k로 나누어 떨어진다면 사용한 동전의 개수를 결과값에 저장시켜줍니다.
그리고 k는 그만큼 값을 차감시키면 끝

코드

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
coin = [int(input()) for _ in range(n)]
coin.reverse()
cnt = 0

for i in coin:
    if k // i > 0:
        cnt += k // i
        k %= i
print(cnt)