[BOJ] 주유소(13305) - PYTHON

문제 설명

N개의 도시가 일직선으로 연결돼있고, 각 도시에는 주유소가 있다. 연결된 도시의 거리 배열, 각 도시의 기름값 정보 배열이 들어올 때 최소의 비용으로 첫 번째 도시에서 마지막 도시까지 가는 비용을 구하는 문제다.
(단, 기름을 실을 수 있는 양은 무한대이며, 기름값과 거리는 10억 이하의 자연수이다. 또한 도시의 개수는 최대 10만 개다.)

시간 복잡도 : O(N)

13305번: 주유소

---

풀이 방법

도시를 차례로 지나가며 소모한 기름 값을 계산할 때, 각각 현재까지 지나온 주유소 중에 기름값이 가장 쌌던 주유소에서 기름을 넣는 것이 제일 이득이다.

ex)
도시 간 거리: 3 8 4 2 5
각 도시의 기름값: 6 7 10 5 3 2
=> 4번째 도시까지 이동할 때는 첫 번째 도시의 주유소에서 기름(기름값: 6)을 넣고 4번째 도시(기름값: 5)에서 5번째 도시에 갈 거리만큼 기름을 넣고, 5번째 도시(기름값:3)에서 마지막 도시에 갈 거리만큼 기름을 넣는다.

따라서 지나온 도시의 주유소 중에 기름값의 최솟값을 담을 변수를 선언하고, 도시를 통과하며  거리 * 최소 기름값을 정답에 차례로 더한다. 또한 마지막 도시의 기름값 정보는 필요 없으므로 사용하지 않는다.
이렇게 하면 거리 배열, 기름값 배열의 같은 index 값에서, 도시 간 거리 * min(현재 index까지의 기름값들)을 정답에 더하면 답을 구할 수 있다.

---

코드

import sys
 
input = sys.stdin.readline
 
N = int(input())
distArr = list(map(int, input().split()))
gasCostArr = list(map(int, input().split()))[:-1]
minGasCost = 10 ** 9 + 1
answer = 0
 
for dist, gasCost in zip(distArr, gasCostArr):
    minGasCost = min(minGasCost, gasCost)
    answer += minGasCost * dist
print(answer)

주석 추가

import sys
 
input = sys.stdin.readline  # input 효율화
 
N = int(input())  # 도시의 갯수
distArr = list(map(int, input().split()))  # 도시간 거리 배열
gasCostArr = list(map(int, input().split()))[:-1]  # 각 도시의 기름값 배열 (마지막 도시의 기름값 정보는 필요X)
minGasCost = 10 ** 9 + 1  # 최소기름값(기름값은 최대 10억이므로 초기값은 10억 + 1)
answer = 0  # 총 기름값
 
for dist, gasCost in zip(distArr, gasCostArr):  # 도시간 거리, 해당 도시의 기름값 (기름값 배열의 마지막 원소가 빠졌으므로 zip을 통해 같은 idx 값끼리 연산한다.)
    minGasCost = min(minGasCost, gasCost)  # 현재까지 지나온 도시들의 기름값 중 최솟값
    answer += minGasCost * dist  # 최솟값 * 거리를 정답에 +
print(answer)
 

---

채점 결과