13305번 주유소

문제

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

접근 방식

최대한 작은 비용으로 갈 수 있는 만큼 가는 게 이득이다. min heap을 활용해서 (비용, 인덱스)를 담아서 그리디 하게 처리했다.

비용 작은 것부터 하나씩 pop 하면서 last_index를 갱신했는데, 이는 현 노드가 갈 가장 먼 거리를 처리하기 위함이다.

코드

from heapq import heappop, heappush
import sys

input = sys.stdin.readline

q = []  # (비용, idx) min heap

n = int(input())
roads = list(map(int, input().split()))
towns = list(map(int, input().split()))
for i, cost in enumerate(towns):
    if i == n - 1:  # 마지막 도시 제외
        break
    heappush(q, (cost, i))  # 최소 비용 순

total = 0
last_idx = n - 1  # 도로의 마지막 인덱스
while q:
    cost, idx = heappop(q)

    if idx < last_idx:
        total += sum(roads[idx: last_idx]) * cost
        last_idx = idx

print(total)