[BOJ/BaekJoon] 백준 11047 동전 0 (Python / 파이썬)

BaekJoon BOJ 백준 11047 동전 0 문제는 여러 종류의 동전을 적절히 사용해서 그 가치의 합을 만들려고 할 때 필요한 동전 개수의 최솟값을 구하는 문제이다.

 

BaekJoon 11047 동전 0 문제 정보

출처

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

알고리즘 분류

- 그리디 알고리즘 (greedy algorithm, 탐욕법)

난이도

- 실버 4 / Silver 4

 

동전 0 문제 요약

• 준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 구하여 출력한다.
  

문제 풀이 과정

동전의 개수가 최소가 되려면 가치가 큰  동전부터 사용하면 된다.
그리디 알고리즘이 정당한 이유는 동전의 큰 가치가 작은 가치의 배수가 되기 때문이다.

 

1. 동전의 종류 수 N, 만들 가치의 합 K, 동전의 가치 A를 입력받는다.
2. A 리스트를 역순으로 하여 큰 가치의 동전부터
3. K를 가치로 나눈 몫을 사용할 동전의 개수에 더한다.
4. 남은 돈을 K에 저장한다.
5. 가장 작은 가치의 동전까지 반복한다.
6. 사용한 동전의 개수를 출력한다.

 

코드 및 설명

• N - 동전의 종류 수
• K - 가치의 합
• A - 동전의 가치가 저장된 리스트
• result - 사용할 동전의 개수
• value - 동전의 가치

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

result = 0
for value in A[::-1]:
    result += (K // value)
    K %= value

print(result)

---

비슷한 문제 풀어보기 >>

[그리디/Greedy] 이코테 거스름 돈 문제 (Python / 파이썬)

[그리디/Greedy] 이코테 거스름 돈 문제 (Python / 파이썬)

 

BaekJoon 백준 BOJ 11047 동전 0 문제를 파이썬 python으로 풀어보았다. 난이도는 Silver 실버 4이다.