백준 11047번 동전 0 (Python)

출처

백준 11047 동전 0

---

정답

import sys 

N, K = map(int, sys.stdin.readline().split())
coins = []
for _ in range(N):
  A = int(sys.stdin.readline().rstrip())
  coins.append(A)

coins.sort(reverse=True)
count = 0
for coin in coins:
  count = count + (K // coin)
  K = K % coin

print(count)

---

문제

---

입출력

---

풀이

0. 전략

위키백과-탐욕_알고리즘

탐욕(Greedy) 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다

큰 동전은 모두 작은 동전의 배수이다  (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
그러므로 동전의 합이 K가 될 때까지 선택할 수 있는 가장 큰 동전부터 선택하면 최적해를 구할 수 있다 
== K 가 0 이 될 때까지 선택할 수 있는 가장 큰 동전부터 K에서 빼주면 최적해를 구할 수 있다

1. 문제/입력값에 의한 초기 설정

# 동전의 종류 N 과 가치의 합 K 
N, K = map(int, sys.stdin.readline().split()) # N = 10, K = 4200
# 동전 주머니 생성 
coins = []
# 동전의 종류만큼 반복해서 입력 처리 
for _ in range(N):
  # 동전을 입력받아 
  A = int(sys.stdin.readline().rstrip())
  # 동전 주머니에 넣기 
  coins.append(A) # [1, 5, 10, 50, 100, 500, 1000, 10000, 50000, 5000]

2. 동전 0 알고리즘

# 가장 큰 순으로 동전을 정렬 
coins = coins.sort(reverse=True) # [50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1]
# 가장 큰 순으로 동전을 정렬     
coins.sort(reverse=True)
# 선택한 동전의 개수 
count = 0
# 동전 주머니의 동전 개수 만큼 반복 처리 : 10회
for coin in coins:
  # 가장 큰 동전으로 나눈 몫을 동전 개수에 추가
  count = count + (K // coin) # 4800 // 1000 = 4
  # K를 동전으로 나눈 나머지로 감소 
  K = K % coin # = K - (K // coin) * coin  = 4800 - (4) * 1000 = 800

3. 정답 출력

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

---

반복 회차별 K의 변화 및 동전 개수 상태

1) N, K = 10, 4200

회차	K	동전개수 및 나머지
1회	4200	50000원 * 0개 및 4200원
2회	4200	10000원 * 0개 및 4200원
3회	4200	5000원 * 0개 및 4200원
4회	4200	1000원 * 4개 및 200원
5회	200	500원 * 0개 및 200원
6회	200	100원 * 2개 및 0원
7회	0	50원 * 0개 및 0원
8회	0	10원 * 0개 및 0원
9회	0	50원 * 0개 및 0원
10회	0	1원 * 0개 및 0원

동전개수 = 1000원 4개, 100원 2개 = 6개

 

2) N, K = 10, 4790

회차	K	동전개수 및 나머지
1회	4790	50000원 * 0개 및 4200원
2회	4790	10000원 * 0개 및 4200원
3회	4790	5000원 * 0개 및 4200원
4회	4790	1000원 * 4개 및 790원
5회	790	500원 * 1개 및 290원
6회	290	100원 * 2개 및 90원
7회	90	50원 * 1개 및 40원
8회	40	10원 * 4개 및 0원
9회	0	50원 * 0개 및 0원
10회	0	1원 * 0개 및 0원

동전개수 = 1000원 4개, 500원 1개, 100원 2개, 50원 1개, 10원 4개 = 12개

---