[백준] 13305 - 주유소 (파이썬, Python)

www.acmicpc.net/problem/13305

13305번: 주유소

---

각 도시 사이의 거리와 도시 별 리터 당 기름 가격이 주어지며 이를 이용해 왼쪽 끝 도시에서 오른쪽 끝 도시까지의 최소 비용을 계산하는 문제입니다!

*기름 1리터 당 1km를 이동할 수 있습니다.

 

이 문제는 기름 값이 싼 도시에서 최대한 많이 주유를 하는 게 핵심이라 생각했습니다.

따라서 아래와 같은 가설을 세웠습니다.

 

현재 도시의 주유 가격과 이전 까지의 최소 가격을 비교

1. 현재 도시의 주유 가격 <= 이전 까지의 최소 주유 가격

-  현재 도시까지의 최소 주유 금액 = (이전에 주유한 도시부터 현재 도시까지의 이동 거리) X (이전까지의 최소 주유 가격)

 

2. 현재 도시의 주유 가격 > 이전 까지의 최소 주유 가격

-  다음 도시로 Pass~!

 

해당 가설을 기반으로 문제 풀이를 한 결과 해결이 됐습니다😁

 

 

전체 코드

import sys

N = int(sys.stdin.readline().strip())
distances = list(map(int, sys.stdin.readline().strip().split()))
prices = list(map(int, sys.stdin.readline().strip().split()))

minPrice = prices[0]
prevIdx = 0
curIdx = 1
answer = 0

while curIdx <= N-1:
    if minPrice >= prices[curIdx]:
        answer += sum(distances[prevIdx: curIdx]) * minPrice
        minPrice = prices[curIdx]
        prevIdx = curIdx

    curIdx += 1
    
if minPrice < prices[-1]:
    answer += sum(distances[prevIdx:]) * minPrice

print(answer)

 

---

해당 문제를 풀고 다른 풀이에 비해 속도가 느린 점이 보였습니다.

확인해본 결과 다른 분들은 대부분 for문을 사용하여 구현을 했습니다.

생각해보니 주어진 개수의 도시들을 순회하는 것이며

for문을 사용할 경우 제 코드의 마지막 부분처럼 조건문이 따로 필요하지 않으므로

해당 문제는 for문의 풀이가 더 적합한 거 같습니다!