[알고리즘][백준] 13305. 주유소

문제

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

 

 

문제 아이디어

맨 앞에서부터 탐색하면서 이전보다 더 적은 가격으로 주유를 넣을 수 있다면 해당 가격으로 주유를 넣으면 되는데, 그래도 최소한의 기름이 있긴 해야하니까 최소한의 기름만 넣으면서 이동하다가 더 싼 가격을 만나면 해당 가격으로 최대한 많이 넣고 이동하면 됩니다. (생각하기 편하게 거리는 일단 전부 2로 했습니다.) 아래와 같은 케이스가 있다고 생각합시다.

	1번 도시	2번 도시	3번 도시	4번 도시	5번 도시	6번 도시	7번 도시	8번 도시	9번 도시
가격	5	2	3	1	8	2	7	4	1
거리	2	2	2	2	2	2	2	2	2

 

1. 일단 처음에는 기름이 아예 없으니까 5원으로 2리터를 넣어줍니다.

2. 2번 도시를 보니까 가격이 2원이네요? 이 때는 1번 도시에서 추가로 넣는 것보다 2번 도시에서 넣는게 좋습니다. 무슨 말이냐면, 1번 도시 -> 3번 도시를 간다고 했을 때 (총 거리 4) 1번 도시에서 4리터를 넣는 것보다 1번 도시에서 2리터, 2번 도시에서 2리터 넣는게 더 싸다는 것입니다.

3. 3번 도시를 보니까 가격이 3원이네요? 이 때는 4번 도시로 갈 때 2번 도시에서 2리터, 3번 도시에서 3리터 넣는 것 보다는 2번 도시에서 아예 4리터 넣고 출발하는 게 더 쌉니다.

4. 4번 도시는 가격이 1원입니다. 지금까지 1번 도시에서 5원 * 2리터, 2번 도시에서 2원 * 4리터를 넣었는데, 이제 앞에 나왔던 어떤 가격보다 싼 1원이 튀어나왔네요. 일단 1원 * 2리터를 넣어줍시다.

5. 5번 도시는 8원인데, 이럴 바에 4번 도시의 1원에서 넣고 오는게 나았죠? 1원 * 2리터를 추가해줍니다.

6. 6번 도시도 2원인데, 이것도 역시 4번 도시의 1원에서 넣고 오는게 나았네요. 1원 * 2리터를 추가해줍니다.

7. ... 

 

결국 현재까지 탐색한 가격을 가장 싼 가격으로 업데이트하면서 과거에 미리 넣고 왔을 지, 아니면 앞으로 해당 가격으로 쭉 넣을지 결정해줍니다.

 

# 4
# 2 3 1
# 5 2 4 1
N = int(input())
road = list(map(int, input().split(' ')))
price = list(map(int, input().split(' ')))

mn = price[0]
result = price[0] * road[0]
for idx in range(1, N - 1):
    mn = min(price[idx], mn)
    result += mn * road[idx]

print(result)