[Python 알고리즘] 백준 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의 배수)

첫번째 케이스
10 4200
1
5
10
50
100
500
1000
5000
10000
50000



두번째 케이스
10 4790
1
5
10
50
100
500
1000
5000
10000
50000

출력

• 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

첫번째 케이스
6



두번째 케이스
12

내가 제출한 풀이 - 정답

import sys

n, k = list(map(int, sys.stdin.readline().strip().strip().split()))
cost_list = [int(sys.stdin.readline().strip()) for _ in range(n)]
res = 0

for i in reversed(range(len(cost_list))):
    mok = k // cost_list[i]
    res += mok
    k -= mok * cost_list[i]

    if k == 0:
        break

print(res)

Tip

• 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

입력 조건을 보다보면 i ≥ 2인 경우에 Ai는 Ai-1의 배수라고 설명이 되고 있다. 이 말은 즉슨, i번째가 2라고 치면 i + 1번째는 2의 배수인 4, 6, 8 ... 이라는 뜻이다. 그러면 i + 2는 i + 1의 배수인 셈이다. 이러한 조건 때문에 입력창은 무조건 오름차순으로 정렬되며, 그리디 알고리즘을 적용시킬 수 있었다. 

 

만약, 이러한 조건이 없다면 

3 800
500
400
100

이런 문제는 어떻게 해결할 것인가?

800원은 500원 1개, 100원 3개보단 400원 2개가 적은 동전의 개수를 사용할 수 있다. 하지만 위와 같은 조건 때문에 이러한 문제는 생각하지 않고 풀어도 된다.

 

reversed()

# range(10) => 0, 2, 3, 4, 5, 6, 7, 8, 9
for i in reversed(range(len(cost_list))):
# reversed(range(10)) => 9, 8, 7, 6, 5, 4, 3, 2, 1, 0


test = ['a', 'b', 'c']
for i in reversed(test):
	print(i)
"""
    c
    b
    a
""""

reversed 함수는 리스트의 요소를 뒤집을 때 사용한다. 즉, 순서가 뒤집힌다고 보면 된다. reversed는 "reversed" 객체를 반환하기 때문에 출력을 할 때는 리스트나 튜플 형태로 변환해줘야 한다.