146. 11047(동전 0) - 파이썬

import sys
input = sys.stdin.readline

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

coinList = sorted([int(input()) for _ in range(N)], reverse = True)
cnt = 0

for val in coinList:
  if K == 0:
    break
  cnt += K//val
  K %= val

print(cnt)

문제요약

주어진 동전 리스트를 최소로 사용하여 가치에 맞게 만드시오

설명

그리디 알고리즘의 대표 문제이다.

그리디 알고리즘에 대해서는 아래를 참고하자

https://smhope.tistory.com/384

[알고리즘 | 자료구조] 그리디 알고리즘(Greedy Algorithm)

 

간단히 설명하면 주어진 상황에 가장 최적인 것을 선택해서 문제를 해결하는 것이다.

 

위 문제에서는 동전리스트를 최소로 사용하고자 하므로 동전 가격이 가장 큰 것 부터 고르면 된다.

coinList = sorted([int(input()) for _ in range(N)], reverse = True)

따라서 주어진 동전리스트를 내림차순으로으로 정리하였다.

 

for val in coinList:
  if K == 0:
    break
  cnt += K//val
  K %= val

매번 가장 큰 동전 부터 시작해서 반복하는 방법도 있지만, 그렇게 하면 시간이 매우 오래걸린다.

따라서 한번 선택한 동전을 가치에서 나눠준 몫을 카운터에 저장한다.

 

예를들어 4200의 가치를 맞추고자 할 때 동전리스트 중에서 1000원이 가장 큰 수라면 1000원이 4장 필요하다.

따라서 4200에서 1000을 나눠 나온 몫 4를 카운트에 저장하고, 4200에서 1000을 나눈 나머지 200은 다음으로 넘긴다.