알고리즘 풀이/백준
백준 13305번 : 주유소 (Python)
heheh
2021. 1. 13. 00:57
문제 : www.acmicpc.net/problem/13305
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
풀이
한칸씩 이동하며 현재 가장 작은 기름값으로 바로 다음 도로를 지나도록 한다.
minoil에 현재 최소 기름값을 넣고
한칸 옮겼을때의 기름값이 더 작으면 minoil을 바꿔서, 더 크면 그대로 두고
바로 다음 길의 길이를 곱하여 결과값에 더한다.
사실상 마지막 주유소는 필요가 없으므로 N-1번만 루프를 돈다.
N = int(input())
road = list(map(int,input().split())) #N-1개
oil = list(map(int,input().split())) #N개
minoil = 1000000001
result = 0
for i in range(N-1):
if oil[i] < minoil:
minoil = oil[i]
result += minoil * road[i]
print(result)