[백준 알고리즘/python] 백준 11047번 동전 0, 파이썬 설명

백준 알고리즘의 그리디 파터 11047번 동전 0 문제를 파이썬으로 풀고, 내가 생각했던 점을 글로 남겨 보려고 한다.

문제 출처

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

먼저 그리디 알고리즘은 단순하게, 뒷 일은 생각하지 않고 지금 당장 좋은 것만 선택하는 알고리즘이다.

이 동전 0 문제의 경우, 특이한 조건이 하나 있어서 그리디 알고리즘을 적용 할 수 있다.

바로, 입력 부분에 있는

파란 줄로 그은 부분이다. 

 

이 말의 의미는, 큰 동전이 전부, 작은 동전의 배수가 된다는 뜻이다. 

이러한 조건이 있기 때문에, 그리디 알고리즘을 사용할 수 있다.

 

문제 해석을 먼저 해 보자

문제 해석

#1. 동전이 총 N 종류가 주어지고, 이 N개의 동전을 적절히 사용해서 합을 K로 만들려고 한다.

#2. 이때, 필요한 동전의 최소값을 구하여라

간단한 문제이다.

 

#생각

#1. 가장 큰 동전부터 시작해서 몫을 카운트 해주고, 나머지 동전을 내림차순으로 반복한다.

 

 

생각을 변환한 코드.

N, K = map(int, input().split()) 
coin_lst = list()
for i in range(N):
    coin_lst.append(int(input()))

count = 0
for i in reversed(range(N)):
    count += K//coin_lst[i] #카운트 값에 K를 동전으로 나눈 몫을 더해줌
    K = K%coin_lst[i] # K는 동전으로 나눈 나머지로 계속 반복

print(count)

 

어렵지 않은 문제이고, 조건만 잘 보면 된다.

만약 800원의 가치를 만들어야 하는데, 500원 400원 100원으로 주어지는 경우는

그리디 알고리즘을 쓰면 안된다.