그리디 알고리즘( greedy) - 1분 정리

그리디 알고리즘 이란? 당장 눈앞에 보이는 죄적의 상황만을 쫒는 알고리즘을 말한다. 

 

코딩 테스트에서 그리디 알고리즘을 사용하여 풀리는 경우가 많다!  하지만 문제를 풀 때 순간순간 최적의 수를 찾아 나아가는 방식은 모든 경우에 최적의 해를 보장할 수 없기에 그리디 알고리즘을 사용하는 경우 최적의 해를 보장하는지 주의해서 살펴야 한다.

 

최적의 해를 보장하지 않는 경우 DP 알고리즘 등 다른 방법을 찾아야 한다.

특정 상황에서는 그리디 알고리즘이 최적의 해를 보장하는 경우도 있다. 대표적인 그리디 문제로는 거스름돈 거슬러 주기 문제가 있다.

 

 

 이 문제를 보면 가능한 큰 숫자의 화폐를 선택하는 방법이 최소한의 화폐를 사용하는 유일한 방법이다. 즉 다시 말해 작은 화폐의 조합으로 최소한의 화폐를 거슬러 줄 수 없다는 것이다! (그리디 해법은 이 문제에서 최적의 해를 보장한다)

 

따라서 이 문제는 그리디 해법으로 해결이 가능하다!

 

N = int(input())
result = 0 
#500,100,50,10 원으로 거스르는 경우 어떻게 하면 최소한의 동전을 사용할 수 있을까?

while N!=0:
  if N%500==0:
    N=N-500
  elif N%100==0:
    N=N-100
  elif N%50==0:
    N=N-50
  else:
    N=N-10
  result=result+1

print(result)