[Algorithm] 그리디 알고리즘 (Greedy Algorithm)

 

 

당장 눈 앞의 최적의 상황만을 좇는 알고리즘,  어느 조건에서는 최적의 해 보장

 

def greedy(n):
    result = 0
    result += int(n / 500)
    n %= 500
    result += int(n / 100)
    n %= 100
    result += int(n / 50)
    n %= 50
    result += int(n / 10)
    print(result)
    
if __name__ == "__main__":
    n = int(input())
    greedy(n)

 

 

def greedy(n):
    result = 0
    div, mod = divmod(n, 500)
    result += div
    n = mod
    div, mod = divmod(n, 100)
    result += div
    n = mod
    div, mod = divmod(n, 50)
    result += div
    n = mod
    div, mod = divmod(n, 10)
    result += div
    print(result)
    
if __name__ == "__main__":
    n = int(input())
    greedy(n)