[백준/Python] 11047번 : 동전 0

시간 제한	메모리 제한	문제 티어
1 초	256 MB	실버 IV

📜 문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

📥입력

📤출력

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

 

💡풀이

저번에 풀었었던 '2720번 : 세탁소 사장 동혁이' 문제랑 닮은 문제이다.

 

https://juni-tech.tistory.com/32

 

 

이 문제를 풀 때 포인트는 일상에서 최대한 동전 안남기고 잔돈 주는 방법을 떠올리면 된다. 가치가 큰 동전부터 차례로 나누어서 줘야 할 동전 수를 세워주면 된다. 결국 List와 반복문을 잘 활용하면 쉽게 풀리는 문제였다.

 

다음은는 내가 작성한 정답 코드이다.

 

import sys

input = sys.stdin.readline

N, K = map(int, input().rstrip().split())

coin_list = [None] * N
count = 0

for i in range(N):
  coin = int(input())
  coin_list[i] = coin

for i in reversed(coin_list):
  count += K // i
  K = K % i

print(count)

이것도 생각해보면 그리디 알고리즘 중 하나라고 볼 수 있다. 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 것이니!