[백준] #11047 동전0(python)

수영·2022년 8월 14일

Python3 백준

백준

목록 보기

37/117

📌문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력

예제 출력

백준 11047번 문제

💡Idea

이런 동전💰 문제는 그리디나 동적계획법을 활용해서 풀 수 있습니다.

저는 그리디를 활용해서 문제를 풀어보았습니다.

동전의 개수를 최소로 만들기 위해서는 큰 가치를 가진 동전을 많이 사용해야 합니다.

예를 들어, 문제의 예제인 4200원을 만들어 봅시다.

1원짜리 4200개
10원짜리 420개
100원짜리 42개
1000원 짜리 4개, 100원 짜리 2개

1원 짜리보다는 10원 짜리가, 그 보다는 100원 짜리가, 그 보다는 1000원까지 사용하는 것이 더 적은 수의 동전을 사용합니다.

큰 가치를 가진 동전을 많이 사용할 수록 더 적은 수의 동전을 사용하게 되는 것이죠!

이렇게 하기 위해서는, 각 선택의 순간에서 가장 최선의 선택을 하면 됩니다.

똑같이 4200원인 경우를 살펴본다면,

4200원을 만들 수 있는 가장 큰 가치의 동전인 1000원 짜리를 4개 사용
남은 200원을 만들 수 있는 가장 큰 가치인 100원 짜리를 사용

위와 같은 순서로 4200원을 만드는 동전을 찾았을 때, 가장 최소의 동전을 찾게 됩니다.

위와 같이 그리디로도 안 풀리는 동전 문제가 있을 수 있습니다. 그럴 때는 동적계획법을 사용하여 풀면 됩니다.

💻코드

⏰ 시간 : 84 ms / 메모리 : 30840 KB

import sys
input = sys.stdin.readline

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

coins = reversed([c for c in [int(input()) for _ in range(N)] if c <= K])
answer = 0

for c in coins:
    if K <= 0:
        break
    answer += K // c
    K %= c

print(answer)