백준 11047. 동전 0 | Python | 그리디

🔔 문제 설명은 백준 문제 링크로 대신합니다.

11047번: 동전 0

 

 

특정 금액을 최소한의 동전 개수로 만들기 위해서는 단위가 큰 동전부터 최대한 많이 사용해야 한다. 큰 동전을 최대로 사용하고, 남은 나머지를 또 최대한으로 쓰고, 그 나머지를 또 최대한으로 쓰고... 이런 식으로 반복해나가다가 나머지가 0이 되는 시점이 오면 계산을 끝낸다. 

 

예를 들어 1300원이 있고, 이를 500원, 100원, 50원짜리 동전을 '최소한'으로 사용하여 구성하려면 무조건 500원짜리를 먼저 최대한 많이, 그 다음에는 100원을 최대한 많이, 마지막으로 50원짜리를 사용해야 한다. 이를 위해 1300원을 500원으로 나눠서 2라는 몫을 얻고 (즉 동전 2개) 300원이라는 나머지가 남으면, 이를 다음으로 가장 큰 동전인 100원으로 나눠서 3이라는 몫을 얻게 된다. 더이상 남은 나머지는 없으므로 50원짜리 동전은 사용되지 않는다. 이때 사용된 총 동전 수는 2+3 = 5 이다. 

 

그리디 알고리즘은 현 시점에서 할 수 있는 최선의 선택을 해 나가는 알고리즘이다. 동전의 경우도, 최소의 수를 사용하기 위해서는 매 시점마다 사용가능한 가장 큰 단위의 동전을 최대한으로 사용해나가는 방식으로 최종 결과를 얻는다. 그리디 알고리즘이 항상 사용 가능한 알고리즘은 아닌데, 지금 상태로는 언제 사용가능한지, 언제 사용가능하지 않은지 까지는 판별이 잘 안된다(ㅠ) 이번 주 내내 그리디 알고리즘을 풀다보면 느낌이 오길 바라본다..

 

코드는 아래와 같다. 

import sys 
input = sys.stdin.readline
N, K = map(int,input().split())
coins= []
for i in range(N):
    coins.append(int(input()))

q = 0 # 동전 갯수들의 총합이 될 변수 
r = K # 동전으로 금액을 나누고 남은 나머지를 담을 변수. 초깃값은 K

for i in range(-1,-N-1,-1):
    q+= int(r/coins[i])  # K를 coin으로 나눈 몫
    r = r %coins[i]
    if r == 0 :
        break

print(q)

핵심은 이 부분인데,

for i in range(-1,-N-1,-1):  
# 입력값이 오름차순으로 주어졌기 때문에 최댓값부터 접근하기 위해  범위를 -1번 인덱스부터 -1씩 줄면서 앞으로 가도록 설정했다. 

    q+= int(r/coins[i])  

# 구해야 하는 수(또는 이전 반복에서 계산하고 남은 나머지)를 사용할 수 있는 가장 큰 동전(coin[i]) 금액으로 나눈 몫이다. 
   몫 자체가 해당 동전의 개수가 되고, 이게 결국 출력해야 할 값이 될 것이므로 누적해서 더해간다.

    r = r %coins[i]
# 구해야 하는 수 (또는 이전 반복에서 계산하고 남은 나머지)를 사용할 수 있는 가장 큰 동전(coin[i]) 금액으로 나눈 나머지이다. 
   이 금액이 0이 아니라면, 다음 반복문에서 그 다음으로 큰 수로 나눠질 것이다. 

    if r == 0 :
        break

# 나머지가 0이라면 계산이 딱 떨어진 것이다. 더 이상 반복문을 실행해도 남은 금액이 없으므로 반복문을 끝낸다. 

 

 

한줄소감: 오히려 문제를 풀때는 모든 게 명확했는데, 이 문제를 정리하는 지금에서야 오히려 만약에 그리디 알고리즘으로 큰 동전부터 썼는데 막상 남은 동전들로 나머지 금액이 딱 맞아 떨어지지 않으면 어떡하지? 하는 생각이 들면서 그리디 알고리즘이 더 멀게 느껴졌다 ^^: 이번 한주 동안 그리디 열심히 공부해봐야지