[그리디 알고리즘] 백준 13305번. 주유소 (파이썬)

백준 13305번 🔗https://www.acmicpc.net/problem/13305

13305번: 주유소

주유소가 중간중간 있는 일직선을 자동차로 이동할 때 최소 주유 요금을 구하는 문제이다. 

 

import sys
input = sys.stdin.readline

N = int(input())

distance = list(map(int, input().split()))
charge = list(map(int, input().split()))

sum = 0
for i in range(N-1):
    sum += charge[i] * distance[i] # 다음 주유소까지 가야하는 만큼 충전
    if charge[i] < charge[i+1]: # 현재 주유소 가격이 다음 주유소 가격보다 더 싸면
        charge[i+1] = charge[i] 
        # 다음 주유소 요금을 현재 요금으로 변경 
        # ∵ 현재 주유소에서 다음 것까지 충전 = 다음 주유소에서 현재 요금으로 충전
        
print(sum)

 

풀이 아이디어를 떠올리는 게 어려운 문제였지만, 방법을 알고 나면 구현은 쉬운 문제이다.

 

🚗 풀이 방법

요금이 비싼 주유소에서는 최소로 충전해야 하고, 요금이 싼 주유소에서는 최대로 충전해야 한다. 

 

만약 현재 주유소 요금이 다음 주유소 요금보다 싸면 다음 주유소에서 충전해야 하는 양도 함께 충전해야 주유 요금을 최소로 만들 수 있다. 

현재 주유소에서 다음 것까지 충전하는 것은 다음 주유소에서 현재 요금으로 충전하는 것과 같다. 

따라서 현재 주유소에서 다음 주유소 요금과 비교한 뒤, 만약 현재 주유소 요금이 더 저렴하면 다음 주유소 요금을 바꿔놓으면 된다.

 

그래서 코드 작성할 때는

1. 각 주유소에서는 다음 주유소까지 필요한 만큼만 충전하고,

2. 최소 요금을 위해 현재 요금 < 다음 요금인 경우 다음 주유소의 요금을 바꿔주면 된다.