[그리디] Python - 13305번, 주유소

www.acmicpc.net/problem/13305

import sys
input = sys.stdin.readline

N = int(input())
distances = list(map(int, input().split()))
prices = list(map(int, input().split()))

curMin = prices[0]
minCost = 0

for i in range(N-1):
    curMin = min(curMin, prices[i])
    minCost += curMin*distances[i]

print(minCost)

우선, 문제를 보고 드는 생각은 가장 싼 곳에서 최대한 많이 주유를 해가면 된다는 것이었다. 그럼, 그 전에는 어떻게 가야하는가? 일반화를 해야하는데, 이것을 설명하기 위해 그림판을 준비했다.

빨간색 직사각형은 각 위치에 대한 가격을 나타낸다.

직관적으로 어디서 얼마나 주유를 해야하는지 감이 오는가? 그 정답은 아래에 있다. 참고로 여기선 거리가 중요한 게 아니므로 거리가 모두 1이라고 가정한다.

즉, 주유를 할 때 생각해야하는 것은, '다음에 이곳보다 싼 곳까지 도달할 정도로 주유를 한다. 이곳이 가장 싸다면 모든 거리에 대해 주유를 한다.'이다. 이 생각을 기반으로, 이제 예시로 주어진 케이스에 대해 거리까지 생각을 해보자.

1. 0번째 도시에서 5*2

2. 1번째 도시에서 2*4

이 두 행동을 하여 18이 되는 것인데, 문제는 이것을 코드로 어떻게 효율적으로 짤 수 있느냐이다. 사실, for문을 돌면서 현재 주유소보다 더 싼 곳에 대해 찾기 위해선 이중 for문이 필요한데, 비효율적이다.

 

이를 위해서, '이미 들렀던 주유소의 가격으로 어느 주유소에서든지 주유할 수 있다.'라는 가정 하에 0~N-1까지 방문하면 된다. for문을 돌면서 일일히, 현재 주유소보다 더 싼 곳까지의 거리를 미리 계산해서 주유를 하고 가야한다는 생각을 버림으로써 코드의 효율이 증가한다는 것이다.

예시 케이스에 대해서 예를 들어보자. 다음은 각 인덱스에서 해야할 행동이다.

0: 5*2

1: 2*3

2: 2*1(중요한 부분, 이전에 2의 가격을 지닌 주유소를 방문하였으므로 이렇게 된다.)

아무튼 이것을 코드화 하면 맨 위에 올린 코드가 된다. 현재까지의 최소값을 갱신해가면서(curMin) 그것에 대해서 for문을 돌며 계산하는 것이다.