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

✨ 그리디 알고리즘(Greedy algorithm)

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식

 

 

 

 

ex)백준 1715번

https://www.acmicpc.net/problem/1715

 

import sys
import heapq

sum=0
hq=[]
for i in range(int(sys.stdin.readline().rstrip())):
    heapq.heappush(hq,int(sys.stdin.readline().rstrip()))
    
sum=0

if(len(hq)==1):print(0)

else:
    while hq:
        a=heapq.heappop(hq)
        b=heapq.heappop(hq)
        sum+=(a+b)
        heapq.heappush(hq,a+b)
        if(len(hq)==1):break

    print(sum)