알고리즘/BOJ
[BOJ 13305, Python 3] 주유소
70825
2021. 8. 1. 13:27
반응형
https://www.acmicpc.net/problem/13305
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
풀이
시작 도시의 기름값을 oil이라는 변수로 잡아두고 한 도시씩 이동하면서, i번째 도시의 기름값이 oil보다 작은지 확인해봅니다.
이때 기름값이 oil보다 작으면 oil의 값을 변경해주고 다시 한 도시씩 이동하면서 윗 줄을 반복합니다.
증명
일단 차가 무조건 이동해야하므로 처음 도시 기름 값을 이용해야 하는 것은 당연합니다.
그러다가 i번째 도시에 도착한 경우를 생각해봅시다.
1) i번째 도시의 기름 값이 지금 사용하고 있는 기름 값보다 비쌀 때
이 경우에는 현재 사용하고 있는 기름을 계속 이용하는 것이 최선입니다.
2) i번째 도시의 기름 값이 지금 사용하고 있는 기름 값보다 쌀 때
기름 값이 더 싸지므로 앞으로는 i번째 도시의 기름 값을 사용하는 것이 최선입니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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)
|
cs |
반응형