[알고리즘][그리디] 그리디

그리디

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

예를 들어 500원, 100원, 50원, 10원 중 최소 개수로 동전을 거슬러 주기 위해서는 가장 큰 동전인 500원 부터 차례대로 큰 순서로 거슬러 주는 방식이 최선일 것이다.

이것은 큰 동전의 순서대로 하위 동전들의 상위 옵션이기 때문에 가능하다.

예를 들어 동전이 500원, 400원, 100원과 같이 주어 졌을 때 800원을 거슬러주기 위해서는 500원 1개와 100원 3개가 아닌 400원 두개를 거슬러 주는 것이 최소 개수를 반환할 수 있게 된다.

이와 같은 경우에는 구현 방식의 알고리즘 풀이가 필요하다.

즉 순서대로 상위 옵션이 하위 옵션을 확실하게 대체할 수 있을 때만 그리디 방식이 유효하다.

---

코드

N = int(input())
cnt = 0

for i in [500, 100, 50, 10]:
    cnt += N // i
    N = N % i

print(cnt)
print(solution(1260))

# 출력 결과
# 6