[파이썬] 단계별 백준 문제 풀기 - 11047 그리디 알고리즘 (동전 0)

문제링크

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

---

 

<<소스코드>>

import sys
n,k = map(int,sys.stdin.readline().split()) #n은 동전 가치의 수, k는 만들어야하는 동전 가치의 값
money = [int(sys.stdin.readline()) for _ in range(n)] #input값, 동전 가치를 리스트로 저장

#동전 갯수 = 우리가 출력할 값
count = 0

#동전가치의 맨 뒤에 값부터 for문 실행
for j in range(n):
    coin = money[n-j-1] #coin은 동전 가치의 가장 큰 값(j가 0일때, money[9] = 50000),
    if k >= coin: #coin이 k보다 작을 때까지 money에서 한단계씩 내려온다. (50000 -> 10000 -> 5000)
        a = k//coin #a는 현재 금액을 나눈 값으로 해당 동전가치에서 필요한 동전의 갯수
        k = k - (a*coin) #이제 새로운 잔액을 k에 업데이트해준다.
        count = count + a 
    if k == 0: # 잔액이 0이면 더 돌 필요없이 for문 탈출 
        break

print(count)

 

<<결과값>>

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

12

---

그리디 알고리즘이란?

 매 순간 최적이라고 생각되는 것을 선택해 나가고, 결국 최종적인 최적해에 도달하는 기법
앞의 선택이 이후 선택에 변화를 주지 않고, 매 순간 선택이 항상 최적이 된다.
동적 계획법보다 효율적이지만 동적계획법보다 반드시 최적의 해를 구해주지는 못한다.

 

대표적인 예제인 동전 문제의 경우, 아래와 같은 방식으로 접근한다.

가장 가치가 높은 동전(예제에서는 50,000원)을 우선으로 거스름돈을 구성하면 동전의 갯수가 줄어든다. 

최적의 해는 최소의 동전을 쓰는 것이므로, 가치가 높은 동전을 최대한으로 쓰는것이 좋다. 

 만약 잔액이 가치가 높은 동전보다 작다면, 동전의 가치를 가장 높았던 것보다 1단계씩 낮춘다(예제에서는 10,000원, 5,000원 순)
 그리하여 k(잔액)값보다 동전의 가치가 작아졌을 때, 몫을 구해서 빼준다.

 그 남은 잔액에 대하여 위의 방식을 반복한다. 그리고 잔액(k)이 0이되면 더 돌 필요 없이 break를 통해 for문을 탈출한다.

 

 

그리디 알고리즘의 개념에대해 처음 배웠는데, 아직은 동적계획법 or 그리디 알고리즘을 언제 써야할지 파악이 안된다.

개념 자체는 dp보다 훨씬 단순한 것 같은데, 단순히 가장 좋아 보이는 것만 선택해도 최적의 해를 구할 수 있는지 구분하는 것이 중요할 것 같다.