백준(BOJ) 11047번 동전 0 [그리디(Greedy)/알고리즘/파이썬(python)]

그리디 알고리즘이란?

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.

 

거스름돈을 돌려주는 문제를 생각해보자.

우리는 대부분 거스름돈을 돌려줄때 큰 단위의 동전부터 거슬러준다.

ex ) 500원을 돌려줘야 한다면, 100원을 5개 주는 것보다 500원을 1개 주는 편이 더 편하다.

 

하지만 만약에 동전의 단위가 100, 250, 300 이라면, (300 * 1) + (100 * 2) 로 3개로 거슬러주는 것보다는 250 * 2 의 방법으로 2개로 거슬러주는 것이 더 최적의 방법이다.

 

따라서 그리디 알고리즘은 항상 최적의 해를 제공해주는 것은 아니다.

하지만 만약 이 상황에서 큰 단위의 수부터 거슬러줘야하는 조건이 존재할 때 그리디 알고리즘이 최적의 해를 제공해 줄 수 있다.

 

---

 

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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

✍ 예제 설명

총 10개의 동전 단위가 주어지고, 4200원을 거슬러줘야할 때 필요한 최소의 동전 개수는?

( 1000 * 4 ) + ( 100 * 2 ) -> 총 6개 이다.

 

👉 알고리즘 설명

큰 수부터 k값과 비교한다.

만약 동전의 단위가 k 보다 작다면 k를 단위값으로 나눈 몫의 숫자를 count에 추가한다.

k값은 그 동전의 단위로 나눈 나머지 값으로 변경한다.

반복하고, k값이 0이 되면 count값을 return 한다.

 

📝 코드

import sys

def count_coin(L, k):
    count = 0
    for i in range(len(L)):
        if k == 0: break
        com = L.pop()
        if com <= k:
            count += k//com
            k %= com
    return count

N, K = map(int, sys.stdin.readline().split())
L = [int(sys.stdin.readline()) for i in range(N)]

print(count_coin(L,K))