[백준 11047번] 동전 0

n, k = map(int,input().split())

value = []
count = 0

for i in range(n):
  value.append(int(input()))

value.sort(reverse=True)

while k!=0:
  for i in value:
    if k//i > 0:
      count += k//i
      k %= i

print(count)

이번 문제는 대표적인 Greedy 알고리즘 문제로, 주어진 동전 단위들을 가지고 최소한의 동전을 사용하여 금액(k)를 만드는 것이 핵심이다.

 

여기서 가장 중요한 조건은 바로 A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수이다.

 

왜 저 조건이 중요한지 생각해보면, 이 문제를 간단하게 탐욕적으로 접근해서 풀 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위에 배수이기 때문이다. (작은 단위의 곱으로 큰 단위를 만들 수 있으므로 작은 단위의 곱으로 만들 필요 없이 큰 단위 하나로 만들면 동전의 개수를 최소화할 수 있기 때문)

 

만약에 저 조건이 없이 동전 단위들이 주어진다면 단순히 탐욕적으로 풀이할 수 없다.

ex) k = 800 , 단위 = [ 500, 400, 100 ] 의 경우, 단순히 탐욕적으로 풀이하면 500 + 100 + 100 + 100 이지만 500과 400은 배수의 관계가 아니기 때문에 풀리지 않는다. 이 경우 정답은 400 + 400 이다.

 

따라서 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 아이디어를 떠올리고 이것이 탐욕적으로 접근하는 것이 정당한지 검토할 수 있어야한다 !