[BOJ 13305, Python 3] 주유소

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

13305번: 주유소

 

 

풀이

시작 도시의 기름값을 oil이라는 변수로 잡아두고 한 도시씩 이동하면서, i번째 도시의 기름값이 oil보다 작은지 확인해봅니다.

이때 기름값이 oil보다 작으면 oil의 값을 변경해주고 다시 한 도시씩 이동하면서 윗 줄을 반복합니다.

 

증명

일단 차가 무조건 이동해야하므로 처음 도시 기름 값을 이용해야 하는 것은 당연합니다.

그러다가 i번째 도시에 도착한 경우를 생각해봅시다.

1) i번째 도시의 기름 값이 지금 사용하고 있는 기름 값보다 비쌀 때

이 경우에는 현재 사용하고 있는 기름을 계속 이용하는 것이 최선입니다.

2) i번째 도시의 기름 값이 지금 사용하고 있는 기름 값보다 쌀 때

기름 값이 더 싸지므로 앞으로는 i번째 도시의 기름 값을 사용하는 것이 최선입니다.

 

코드

n = int(input())
road = [*map(int, input().split())]
city = [*map(int, input().split())]
 
oil = city[0]
ans = 0
 
for i in range(1, n):
    ans += road[i-1] * oil
    if city[i] < oil: oil = city[i]
 
print(ans)