[백준(BOJ)] 13305번 주유소 - 파이썬/python

문제

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

13305번: 주유소

n개의 도시를 연결하는 도로의 길이와 주유소의 리터당 가격이 주어진다. 주유소에서 기름을 넣고 출발해야 하는데, 제일 왼쪽 도시부터 제일 오른쪽 도시로 가는 최소 비용을 구하는 문제다.

예시

Example 1:

Input: 4
     2 3 1
     5 2 4 1
Output: 18

 

Example 2:

Input: 4
     3 3 4
     1 1 1 1
Output: 10

풀이

import sys
input = sys.stdin.readline

n = int(input())
road_len = list(map(int, input().split()))
price = list(map(int, input().split()))

# 첫 번째 주유소의 가격을 최소 가격으로 초기화
min_price = price[0]
ans = 0

for i in range(n - 1):
  # 현재 도시의 주유소 가격이 현재까지 최소 가격보다 작으면 최소 가격 업데이트
    if min_price > price[i]:
        min_price = price[i]
  # 현재 도로를 이동하는데 드는 비용 계산
    ans += (min_price * road_len[i])

print(ans)

 

- 그리디 알고리즘을 활용하여 각 단계에서 최적의 선택을 하며 최소 비용을 구한다.

- 첫 번째 주유소의 가격으로 최소 가격을 초기화하고, 반복문을 통해 마지막 도시 전까지 각 도시를 탐색하며 주유소 최소 가격과 거리를 곱해 비용을 계산한다.