백준 13305번 주유소 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 13305 주유소

13305 주유소

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

13305번: 주유소

한 방향(왼쪽에서 오른쪽)으로 도시를 이동해야 하므로 리터 당 가격을 비교하며 이동하는 방법으로 풀이했다.

요즘 기름 값이 비싸긴 하다...

 

알고리즘 분류

• 그리디 알고리즘

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())
dist = list(map(int, input().split()))
price = list(map(int, input().split()))
result = 0
a = price[0]

for i in range(n-1):
    if price[i] < a:
        a = price[i]
    result += a * dist[i]

print(result)

---

풀이

주유소들 사이의 거리는 n보다 1작다, 이 거리들을 이동하면서 연료 값을 비교해야 한다.

출발 시에는 첫 주유소를 이용해야만 한다. 다음 주유소까지 이동한만큼 가격에 곱하여 준다.

두 번째 주유소부터는 현재 값 a와 비교하며 더 작다면 그 주유소 가격을 이용하고 비싸다면 전 주유소의 가격을 다시 곱한다.

처음 문제를 볼 때는 어려울 것 같았으나 막상 풀이해보면 간단한 문제였다. 

---

풀이 결과

13305 풀이 결과