Python/Greedy BOJ-13305 주유소

Posted on | In

[Python/Greedy] BOJ-13305 주유소

📌문제링크

오른쪽 도시로 갈때 사용하는 최소 비용을 구하는 문제다.
주유소별 가격비교를 하면서 min_cost를 조절해주면 된다.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
input = sys.stdin.readline

if __name__ == '__main__' :
    N = int(input()) # city
    dist = list(map(int,input().split())) # distance
    cost = list(map(int,input().split())) # oil cost
    min_cost = cost[0]; result=0; total_dist = sum(dist)
    for i in range(len(dist)):
        if cost[i] == 1 : #최소 비용일 경우를 만나면 더이상 학인할 필요없음
            result += total_dist
            break
        elif cost[i] <= min_cost :
            min_cost = cost[i]
        result += dist[i]*min_cost
        total_dist -= dist[i]
    print(result)