[BOJ] 13305 주유소

👉 들어가기

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

greedy algorithm 에 해당하는 기본적인 문제입니다.
반복문을 돌면서, 현재 도시의 가격(price[i]) 와 바로 다음 도시의 가격(price[i+1])을 비교하여 현재 도시의 가격이 더 저렴할 때,
다음 도시의 가격도 현재 도시의 가격으로 바꿔주기만 하면 됩니다.

현재 도시에서 최소한 가야하는 거리 만큼을 현재의 index 에서 total에 더해주면서 반복문을 진행합니다

✏️ 문제 풀이

from sys import stdin
input = stdin.readline

n = int(input())
city = list(map(int, input().split()))
price = list(map(int, input().split()))
total = 0

for i in range(n):
    if(i < n-1):
        if (price[i] < price[i+1]): # 현 도시의 가격이 다음 도시의 가격보다 적을 경우
            price[i+1] = price[i] # 현재 도시의 가격으로 바꿔 준다.
        total += price[i] * city[i] # 반복문을 진행하면서, 가격을 더해준다.
print(price)