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

시간제한 : 1초

메모리제한 : 256MB

문제 :

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

 

---

 

그리디 알고리즘?

그리디 알고리즘에 해당하는 문제.

 

그리디 알고리즘은 문제를 해결하기 위한 가장 직관적인 알고리즘 중 하나로, '탐욕'(greedy)이라는 단어가 암시하듯 현재 상황에서 가장 최적의 방식을 택하는 방식으로 문제의 답을 도출하는 방식이다. 

 

1000원 지폐와  500원, 100원 동전이 있을 때, 가장 적은 숫자의 화폐로 2600원을 만들어야 하는 상황을 가정해보자. 

이 문제를 풀기 위해 그리디 알고리즘을 적용하면 다음과 같은 절차를 수행한다. 

1) 가장 큰 화폐인 1000원을 적용하면, 1000원 지폐 2개를 사용하고 600원이 남음.

2) 600원이 1000보다 작으므로, 1000을 적용할 수 없다. 따라서 다음으로 적용 가능한 수인 500원을 1개 사용하고, 100원이 남음.

3) 100원은 1000과 500보다 작으므로, 다음으로 적용 가능한 수인 100원을 1개 사용하여 2600원 완성.

 

그러나 그리디 알고리즘을 통해 찾은 해는 최적의 해가 아닐 수 있다.

동전의 종류가 500원, 400원, 100원이고, 최소한의 개수를 사용해 800원을 만들어야 하는 경우를 생각해보자.

그리디 알고리즘을 적용한다면, 

(1) 500원 1개 -> 남은 금액 300원 (2) 400원 x (3) 100원 3개 -> 남은 금액 0원 

필요한 동전의 개수는 4개로 나온다.

 

그러나 800원은 400원 동전 2개만 사용해도 만들 수 있다. 

 

따라서 그리디 알고리즘은 편리한 문제 해결 방식이지만, 항상 최적의 해를 보장하지는 않는다. 따라서 그리디 알고리즘을 적용할 때에는, 그리디 알고리즘에 적합한 문제인지를 먼저 파악하는 것이 중요하다. 

 

풀이

이 문제는 그리디 알고리즘을 적용하여 해결할 수 있다.

왜냐하면 최소한의 동전으로 목표하는 금액을 만들기 위해서는 가능한 가장 큰 금액부터 먼저 살펴보는 것이 가장 좋은 방법이기 때문이다. 

 

따라서 입력받은 동전을 가장 큰 순서대로 정렬한 후,

목표하는 금액에서 가장 큰 동전부터 나누어 몫을 동전 개수에 더한다. 

 

이후 목표하는 금액 - (가장 큰 동전 * 몫)을 한 다음,

위의 절차를 반복하여 목표하는 금액이 0이 되면 반복문을 종료하고 지금까지 합산한 동전 개수를 출력한다.

N, K = map(int, input().split())
coins = []

for _ in range(N):
    coins.append(int(input()))

coins.sort(reverse=True)

cnt = 0

for coin in coins:
    coin_num = 0
    if K <= 0:
        break
    else:
        coin_num += K // coin
        cnt += coin_num
        K -= coin_num * coin
print(cnt)