백준 13305 주유소

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

13305번: 주유소

📌 해결순서

문제는 길고 복잡해 보이지만 문제를 이해하고 나서, 딱 그리디 유형의 표준문제라고 생각했다.

문제를 이해한 후 내가 생각한 해결 아이디어는 다음과 같다.

 

1. 첫번째 도시에서 다음 도시로 가기 위해서는 첫번째 도시의 기름 가격이 얼마든지 상관없이 기름가격 * 도로길이 만큼 비용을 사용한다

2. 두번째 도시부터는 첫번째 도시의 기름가격보다 두번째 도시의 기름가격이 더 싸면 두번째 도시의 기름을 사용하고 아니면 첫번째 도시의 기름을 계속 사용한다

3. 모든 도시의 기름 가격을 반복해서 비교하면서 마지막 도시까지 이동한다

4. 마지막 도시는 주유소를 사용하지 않기 때문에 비교 대상이 아니다.

📌 코드

import sys
input = sys.stdin.readline

n = int(input())
road = list(map(int, input().split()))
oils = list(map(int, input().split()))

curr_cost = oils[0]
cost = curr_cost * road[0]

for i in range(1, n - 1):
    if(curr_cost > oils[i]):
        curr_cost = oils[i]

    cost += curr_cost * road[i]

print(cost)