BOJ 13305 : 주유소

13305 : 주유소

풀이

이 문제는 다음과 같은 흐름으로 풀면 쉽게 풀 수 있다.

1. 단방향으로 노드를 순회 하면서 가장 낮은 값을 갖는 노드의 가중치를 기억한다

2. 같은 인덱스에 있는 {간선의 가중치} x {노드의 최소 가중치} 값을 구해 결과 변수에 더해준다

이 문제를 풀 때, 유의해야 될 부분은 단방향 순회의 범위를 지정하는 부분이라고 볼 수 있다.

문제의 조건을 보면,

1. 노드의 개수 = 4

2. 간선의 개수 = 3

3. '처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다'

위 조건 중 3번 조건에 따라 반복문에 들어가 전, 먼저 첫번째 노드와 첫번째 간선의 데이터는 계산되어야한다.

또한 맨 마지막 노드의 경우 다음 노드로 가는 간선이 없기 때문에
무시해도 된다.

그래서 실질적으로 반복문이 수행되어야 할 범위는
빨간색 상자로 표시 된 부분 index 1~2 부분이 된다.

이 점을 유의하며 코드로 구현하면 다음과 같다.
(코드는 Python3 문법을 따른다)

n = int(input())
load = list(map(int, input().split()))
node = list(map(int, input().split()))

m = node[0]
res = m * load[0]

for i in range(1, n-1):
    if node[i] < m:
        m = node[i]
    res += (m*load[i])
print(res)