백준 5585. 거스름돈 (파이썬 - 그리디)

문제를 요약하면..

전형적으로 쉬운 그리디 알고리즘 문제이다

가장 최소의 동전개수로 거스름돈을 거슬러주기!

시도 1 (정답)

Point!

1) 가장 큰 동전부터 거슬러 주는 방법이 최소의 동전으로 거슬러주는 방법이다.

2) 각 동전에 근접한 배수를 구하고 -> 뺀 나머지에서 또 다른 동전의 근접한 배수를 구하고 -> ...-> 돈이 0원 될 때까지 반복한다.

※이 2번 Point는 그리디 문제 중 전형적인 문제에서 많이 사용할 수 있는 중요한 Tip 이다!!

Ex. 어떤수 207을 1로 만들기 위해 /2, -1 두 방법만 사용할 수 있을 때, 최소한의 방법으로 1만드는 방법 구하기

이때 2의 배수이면 나누고, 홀수이면 -1하며 계속 for문을 돌리는 것보다

207에 근접한 2의 배수를 구하고, 그 몫과 나머지 값을 더하면 최소한의 방법이 나온다.

그러면 복잡도도 O(N)에서 O(logN)으로 줄일 수 있다!