백준 | [파이썬 Python] 13305 주유소

 

---

배경

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

 

 

 

코드

import sys
input = sys.stdin.readline
n = int(input())
dist = list(map(int, input().split()))
price = list(map(int, input().split()))
result = 0
maxx = price[0]
for i in range(n-1):
    if price[i] < maxx:
        maxx = price[i]
    result += dist[i]*maxx

print(result)

 

 

설명

방법만 알면 어렵지 않은 문제이다.

가장 값이 적은 주유소를 추적하면서 거리를 곱해주면 된다

for문을 돌면서 새로운 주유소가 이 전 주유소 보다 값이 큰 지 확인한다.

아니라면 그 전 주유소에서 다음으로 이동 하는데 필요한 기름을 넣어 주면 된다.

 

 

배운 점

예전 소마 테스트에서 비슷한 문제가 나왔었는데 그때는 dfs라고 생각했는데 지금 보니 그리디 문제인가? 싶다