[BOJ] 13305. 주유소

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

13305번: 주유소

 

 

1. 해결방법

"""
1. 아이디어
- 첫 도시의 기름 값을 min_v로 설정
- 각 도시의 기름 값을 리스트로 두어서 min_v랑 비교해서 더 작으면 갱신
- 만약에 더 작다면 이전의 도시의 기름 값을 도시 간의 거리에 곱을 add_v에 더한다.

2. 시간복잡도
- O(N)
"""

 

 

2. 정답코드

import sys
input = sys.stdin.readline

N = int(input())
roads = list(map(int, input().split()))
cities = list(map(int, input().split()))

min_v = cities[0]
cost = 0

for i in range(N - 1):
    min_v = min(cities[i], min_v)
    cost += min_v * roads[i]

print(cost)

그리디 문제를 몇번 접하다 보니 조금은 쉽게 느껴졌던 문제다.
하지만 아직은 아이디어를 코드에 다 담기는 무리가 있는 것 같다... 더 풀어보자