[그리디 알고리즘] 백준 11047번 동전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	예제 출력 1
10 4200 1 5 10 50 100 500 1000 5000 10000 50000	6
예제 입력 2	예제 출력 2
10 4790 1 5 10 50 100 500 1000 5000 10000 50000	12

---

아이디어

동전의 종류는 N가지이며 동전의 개수는 무한개이다.('각각의 동전을 매우 많이 가지고 있다.'라고 문제에 언급) 
따라서 N가지 동전을 이용하여 합이 K가 될 수 있도록 하는 동전 개수의 최솟값을 구하는 문제이다. 
이 문제에서 전체적인 최적해는 합을 K로 만드는 최소 동전 개수이며, 부분적인 최적의 선택은 큰 가치를 가지는 동전의 개수를 최대화하는 것이다.  

---

변수 설명(솔루션과 코드)

N: 준규가 가지고 있는 동전의 종류   
A: 주어진 동전의 가치를 저장하는 배열   
K: 처음에는 최종적으로 만들어야 하는 가치의 합을 저장, 이후 단계에서는 다음 단계에서 채워야 하는 금액(즉, 나머지 금액)을 저장한다.  
ccount: 각 단계별로 사용되는 동전의 개수를 저장. 
csum: 각 단계별로 사용되는 동전의 개수를 합하기 위해 사용

---

솔루션

각 단계는 가치가 큰 동전부터 내림차순으로 진행되어야 한다. (큰 가치를 가지는 동전의 수를 최대화 하기 위해)
첫 번째 단계에서는 K원을 넘지 않으면서, 사용할 수 있는 가장 많은 A[0] 개수를 선택한다. (이 때 사용가능한 동전의 최대 값은 ccount인 K//A[0] (K를 A[0]로 나눈 몫)이다.) 선택한 값을 csum에 저장하고, K에서 A[0]*ccount(동전의 금액 * 동전의 최대 개수)를 뺀 값을 K에 저장한다.(이 때 K에 저장되는 금액은 다음 단계를 통해 만들어야 하는 나머지 금액이다.) 다음 단계에서도 K를 넘지 않으면서, 사용할 수 있는 가장 많은 동전(ccount)을 csum에 더하고 K에는 이번 단계에서 채운 금액을 제외한 나머지 금액만을 저장하는 최적 선택을 반복한다.

나머지가 0원인 경우 반복문을 탈출하여 전체적인 최적 해, 즉 현재까지 선택한 각 단계의 동전 개수를 모두 합한 csum를 출력한다.

---

코드(Python)

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

A = []
for _ in range(N):
    A.append(int(input()))
A = sorted(A, reverse = True) # 배열 A를 큰 수부터 내림차순으로 정렬

for i in range(N):
    ccount = K//A[i]
    csum += ccount
    K -= (ccount)*A[i]
    if K == 0: # 나머지 금액이 0인 경우 반복문 탈출
        break
        
print(csum)

 

설명에 잘못된 부분이 있거나 질문 사항이 있으시다면 언제든지 댓글 남겨주세요 :)