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

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

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

 

해결코드

n,k = map(int, input().split())
li = []
cnt = 0
for i in range(n):
    li.append(int(input()))
li.reverse()
for i in range(n):
    cnt += k//li[i]
    k = k%li[i]
print(cnt)

문제풀이

주어진 동전의 종류를 가지고 최소한의 동전 개수로 주어진 돈을 만들어야 하는 문제이다.

일단 n에 동전의 종류가 몇개인지 입력받고 k에는 만들어야하는 돈 크기를 받아준다.

그리고 동전의 종류를 넣을 li라는 리스트를 하나 선언해준다.

동전이 몇개 필요한지 넣을 cnt를 선언하고 0으로 초기화해준다.

for문을 이용하여 n개만큼 li에 동전의 종류를 추가해준다.

그리고 li.reverse()를 통해서 리스트를 거꾸로 뒤집어주는데

그 이유는 --> 현재 동전 크기를 오름차순으로 입력받았는데, 그리디 알고리즘을 통해

이 문제를 해결하려면 먼저 구해야하는 돈의 크기와 근접한 동전부터

돈의 크기를 그 동전으로 나누었을 떄 나머지를 카운트에 더해주고

그 나머지로 계속해서 내림차순을 반복해주면 된다.

그렇게 하면 최소한의 동전으로 원하는 돈 크기를 맞출 수 있다.

k가 li[i]보다 작다면 몫은 0이 나오고 나머지로 k가 그대로 나오므로

계속해서 내림차순을 이어나갈 수 있다.

그렇게 반복해서 얻은 cnt를 출력해준다.