[BOJ] 백준 13305 주유소

태환·2024년 2월 2일
0

Coding Test

목록 보기
38/151

📌 [BOJ] 백준 13305 주유소

📖 문제


📖 예제

📖 풀이

N = int(input())
E = list(map(int, input().split()))
V = list(map(int, input().split()))

total = 0
cost = V[0]
for i in range(N-1):
  if V[i] * E[i] < cost * E[i]:
    total += V[i] * E[i]
    cost = V[i]
  else:
    total += cost * E[i]

print(total)

총 주유 비용을 최소화하기 위해서 새로운 정점에 도달할 때 마다 기존 정점의 주유 비용과 비교하고 낮을 경우 가지고 있던 기존 주유 비용을 새로운 정점의 주유 비용으로 초기화시킨 후 다음 간선인 거리와의 곱을 총 주유 비용에 더하는 수행을 반복한다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글