[백준] 13305번: 주유소 - 파이썬

📎문제링크: https://www.acmicpc.net/problem/13305

13305번: 주유소

 

🧩문제 해석

전형적인 그리디 문제!
왼쪽에서 오른쪽으로 이동하는데 기름값을 가장 아끼며 주유하는 방법을 찾는거였다. 기름통의 한계는 없다고 주어졌기에 방법은 간단하다. 조금씩 조금씩 주유해가다가 가장 저렴한 주유소에서 가득 채운다음 가면 된다.

 

📘풀이

현재 주유소의 기름값하고 다음 주유소의 기름값하고 비교해가면서 기름값을 갱신하고 거리수랑 곱해준다.

 

💻코드

n = int(input()) # 주유소 갯수
road = list(map(int, input().split())) # 거리
coin = list(map(int, input().split())) # 기름값
result = 0
cheap = coin[0] # 출발하려면 우선 첫 주유소에서 주유해야함
for i in range(n-1):
    result += road[i]*cheap # 나아갈 거리랑 현재의 기름값이랑 곱한다.
    if cheap <= coin[i+1]: # 다음 주유소보다 저렴하다면 패스
        pass
    else: # 다음 주유소보다 비싸다면 cheap를 다음 주유소로 갱신
        cheap = coin[i+1]
print(result)

 

 

역시 그리디 방법 찾아내는건 재미지다ㅎ.ㅎ