그리디

• 탐욕법
• 현재 상태에서 계속 BEST를 선택 ➡️전체 선택 중 BEST라고 가정하는 알고리즘
• ⚠️ 항상 최적의 해를 보장하지는 않는다.
  • 그리디로 풀어도 되는지 안되는지 판단하는 것이 중요하다.
  • 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 한다.
• ex) 거스름 돈 문제

수행 과정

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

백준 1715

• 그리디 + 힙 자료구조

import sys
import heapq

input = sys.stdin.readline

N = int(input())
cards = [int(input()) for _ in range(N)]
heapq.heapify(cards)

result = 0

while len(cards) > 1:
    a = heapq.heappop(cards)
    b = heapq.heappop(cards)
    heapq.heappush(cards, a + b)
    result += a + b

print(result)