[백준]13305번 주유소 - 그리디

 

import sys

n = int(input())

length = list(map(int, sys.stdin.readline().split()))
oil = list(map(int, sys.stdin.readline().split()))
sum_ = 0
min_ = 0
for i in range(n - 1):
    if i == 0:
        sum_ = oil[0] * length[0]
        min_ = oil[0]
    else:
        min_ = min(min_, oil[i])
        sum_ = sum_ + min_ * length[i]
print(sum_)

 

코드 설명

길이와 기름 값 가격을 리스트에 저장하여 둔다. 반복문을 n-1 번 수행한다. 만약 맨 처음일 경우 첫 도로의 길이 * 첫 도시의 가격을 통해 기름을 넣어준다. 다음 도시에 도착하였을 때 기름 가격을 비교 한 후 더 싼 가격을 선택하여 도로의 길이만큼 또 전진한다. 

위와 같이 반복하며 정답을 구할 수 있다.

 

Point : 최솟값을 기억하는 방식을 이용한다. 도시를 이동해가며 적은 기름 가격을 매번 체크하면서 적은 양을 선택해서 기름을 넣도록 한다.

일반적인 상식과 달리 먼저 도시를 이동한 후 기름값을 지불하는 방식으로 생각하면 이해하기 쉽다.