[그리디/Greedy] 백준 11047 동전 0 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11047번: 동전 0

 

 

 

2. 문제 풀이

 주어진 동전 단위 내에서, 최소 동전 개수로 거슬러주는 문제입니다.

 

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 문제의 입력 조건에서, 높은 동전 단위는 낮은 동전 단위의 배수가 된다고 한정했습니다. 동전 단위가 배수로 커질 때, '탐욕스런 선택조건'을 만족하므로 해당 문제는 그리디 알고리즘으로 풀 수 있습니다.

 탐욕스런 선택조건은 '앞의 선택이 이후 선택에 영향을 주지 않아야 한다'는 조건입니다. 동전 단위가 배수로 이루어져 있을 때는 무조건 높은 단위로 거슬러 주는 게 최적입니다. 실생활의 동전 단위도 배수로 이루어져 있으며, 우리도 무의식적으로 높은 단위부터 거스름돈을 계산합니다.

 ex) 거스름돈 660 => 500*1 + 100*1 + 50*1 + 10*1

 

 

 

3. 코드

N, K = map(int, input().split())
coin = []
for i in range(N):
    coin.append(int(input()))

res = 0
for c in coin[::-1]:
    if c <= K: # 남은 돈이 동전 단위보다 같거나 큰 경우 (거슬러줄 수 있는 경우) 
        res += K//c
        K %= c
print(res)

 

 거슬러줘야 하는 돈의 액수(K)와 동전 단위를 입력받습니다.

 그리디 알고리즘을 이용하여, 큰 동전 단위부터 거슬러줍니다.