[BOJ] 13305 - 주유소

풀어보기

접근

1. km당 1L의 기름을 사용한다. 연비가 좋지 않다
2. 기름은 무제한으로 주유할 수 있으며 각 도시마다 싯가로 판매한다.

무조건 가장 싼 곳에서 주유를 하는게 이득이다. 하지만 가장 싼 곳까지 가려면 어딘가에서 주유를 하여야 한다...
내가 생각한 방법은 다음과 같다.

1. 일단 가장 싼 곳 $C_i$을 찾는다.
2. 그곳에서 최대한 주유하여 마지막 지점 $B$까지 가는 경우의 비용을 계산한다.
       2-1. 그 후 출발지점 $A$에서 $C_i$ 범위 내에서 가장 싼 곳을 찾는다.
       2-2. 그곳에서 최대한 주유하여 $C_i$까지 가는 경우의 비용을 계산한다.
           ...

코드 1 - 58점짜리 코드(...)

from sys import stdin

N = int(stdin.readline())
road_len = [int(i) for i in (["0"] + stdin.readline().split())]
oilbank = [int(i) for i in stdin.readline().split()]

total_cost = 0

def search(begin, end):
    global total_cost, N, road_len, oilbank

    if begin == end:
        return

    min_idx = begin

    for candidate in range(begin, end):
        if OILBANKS[candidate] < OILBANKS[min_idx]:
            min_idx = candidate

    total_cost += sum(ROAD_LENGTH[min_idx + 1 : end + 1]) * OILBANKS[min_idx]
    search(begin, min_idx)

search(0, N)
print(total_cost)

위 아이디어를 그대로 구현한 코드로, 도로 길이 배열 road_len과 기름값 배열 oilbank의 길이를 맞추기 위해 도로 길이 배열의 0번째에 0을 추가해주었다. 그 다음 범위 내 가장 싼 주유소에서 가장 멀리까지 이동하는 경로를 재귀적으로 구해준다.
$O(n^2)$의 시간복잡도 덕분인지 끝내 마지막 서브테스크는 통과하지 못했다.

코드 2 - 100점짜리 코드

from sys import stdin

N = int(stdin.readline())
road_len = [int(i) for i in stdin.readline().split()]
oilbank = [int(i) for i in stdin.readline().split()]

total_sum = 0
current_min = 1_000_000_001

for i in range(N - 1):
    current_min = min(current_min, oilbank[i])
    total_sum += road_len[i] * current_min

print(total_sum)

top-down이 아닌 bottom-up으로 문제를 보면 $O(n)$에 문제를 해결할 수 있다는 점을 깨닫고 그렇게 구현해보았다. 또한 어차피 기름값 배열 oilbank의 가장 마지막 요소는 사용하지 않으므로 도로 길이 배열 road_len에 추가적인 수정을 할 필요가 없다는 점을 깨닫고 그렇게 구현해보았다.

아이디어는 큰 고민 없이 생각해낼 수 있었으나 이를 구현하는 과정에서 삽질을 했다. 한 아이디어를 생각해낸 뒤부터 다른 선택지는 고려하지 않는 경향이 있는 것 같다. 보다 열린 사고를 가지고 문제를 풀어보자.