백준 13305 주유소 Java: 지금까지의 최저 가격을 쓰는 그리디

백준 13305번 주유소는 일직선에 놓인 도시를 왼쪽에서 오른쪽으로 이동할 때 필요한 최소 주유 비용을 구하는 문제다. 각 구간의 거리와 각 도시의 리터당 가격이 주어지고, 연료통 용량에는 제한이 없다.

처음 문제를 봤을 때는 PriorityQueue를 떠올렸다. 하지만 이동 방향이 한쪽으로 고정돼 있고, 현재 구간을 지나기 전에 방문한 주유소에서만 기름을 살 수 있다는 점을 보니 더 단순한 규칙이 보였다.

각 도로 구간은 지금까지 만난 주유소 가격 중 가장 싼 가격으로 계산한다.

당시 단계별 문제의 greedy 부분을 마친 직후라 이 규칙을 빠르게 찾을 수 있었다. 이어질 정수론·조합론 단계를 앞두고 막막한 마음도 있었지만, 이 문제는 greedy의 선택을 증명하는 연습으로 다시 보기 좋았다.

현재보다 싼 주유소를 만날 때까지 산다

예시를 단순화해 보자.

도시 가격:   5       2       4       1
도로 거리:      2       3       1

첫 도시에서는 가격이 5다. 다음 도시의 가격 2가 더 싸므로 첫 도로 2km에 필요한 기름만 가격 5로 산다.

두 번째 도시에서는 지금까지 가장 싼 가격 2를 만났다. 세 번째 도시의 가격 4는 더 비싸므로 두 번째와 세 번째 도로에 필요한 기름을 가격 2로 산 것과 같은 비용이 든다.

2 × 5 + 3 × 2 + 1 × 2 = 18

구현에서는 실제 주유량을 미리 묶어 계산할 필요가 없다. 도로를 하나씩 지나며 현재까지의 최저 가격을 갱신하면 같은 결과가 나온다.

왜 이 선택이 항상 최적인가

왼쪽에서 i번째 도로를 건너려면 그 도로에 도착하기 전 도시 중 한 곳에서 기름을 사야 한다. 아직 방문하지 않은 오른쪽 도시에서는 과거 구간에 쓸 기름을 살 수 없다.

i번째 도로 이전에 본 가격의 최솟값을 minPrice라고 하자.

• minPrice보다 비싼 도시에서 그 구간의 기름을 살 이유가 없다.
• 연료통 용량이 무제한이므로 minPrice인 도시에서 필요한 만큼 미리 살 수 있다.
• 따라서 그 구간의 최소 비용은 distance[i] × minPrice다.

이 논리를 모든 구간에 적용하면 전체 비용도 최소가 된다.

exchange argument로도 볼 수 있다. 어떤 최적해가 한 구간의 기름을 과거의 더 비싼 도시에서 샀다고 가정하자. 그 양을 지금까지 가장 싼 도시에서 산 것으로 바꾸면 경로의 feasibility는 유지되고 비용은 줄거나 같다. 따라서 최저 가격만 사용하는 최적해가 항상 존재한다.

마지막 도시의 가격을 쓰지 않는 이유

도시가 N개면 도로는 N - 1개다. 마지막 도시에 도착한 뒤에는 더 건널 도로가 없으므로 마지막 주유소 가격은 정답 계산에 사용되지 않는다.

입력에는 가격이 N개 주어지므로 모두 읽되, loop는 N - 1개 도로만 처리한다.

Java 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int cityCount = Integer.parseInt(br.readLine());
        long[] distances = new long[cityCount - 1];
        long[] prices = new long[cityCount];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < cityCount - 1; i++) {
            distances[i] = Long.parseLong(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < cityCount; i++) {
            prices[i] = Long.parseLong(st.nextToken());
        }

        long minimumPrice = prices[0];
        long totalCost = 0L;

        for (int i = 0; i < cityCount - 1; i++) {
            minimumPrice = Math.min(minimumPrice, prices[i]);
            totalCost += minimumPrice * distances[i];
        }

        System.out.println(totalCost);
    }
}

원래 풀이처럼 가격 array 자체를 prefix minimum으로 바꿔도 맞는다. 이번 코드는 입력값을 덮어쓰지 않고 minimumPrice라는 상태 하나에 의미를 드러냈다.

long을 써야 하는 이유

도시 수는 최대 100,000이고, 전체 도로 길이와 리터당 가격은 각각 최대 1,000,000,000이다. 가능한 비용은 int의 최댓값을 쉽게 넘는다.

예를 들어 총거리와 사용 가격이 모두 1,000,000,000이면 곱은 10^18이다. 이는 Java long 범위에는 들어가지만 int에는 들어가지 않는다.

long totalCost = 0L;
long minimumPrice = prices[0];

곱셈의 operand도 long이어야 한다. 결과를 long 변수에 담더라도 두 operand가 먼저 int로 곱해지면 이미 overflow가 난 뒤다. 이 풀이에서는 distances와 prices를 처음부터 long[]으로 읽어 그 위험을 피했다.

PriorityQueue가 필요하지 않은 이유

우리가 필요한 값은 “지금까지 본 가격 중 최솟값 하나”뿐이다. 과거 가격 전체를 꺼내거나 순서를 바꿔 처리하지 않는다.

minimumPrice = min(minimumPrice, currentPrice)

이 한 줄이면 prefix minimum이 유지된다. PriorityQueue를 쓰면 삽입과 조회 구조를 추가하고도 문제의 시간 순서를 더 잘 표현하지 못한다.

• 시간 복잡도: O(N)
• 공간 복잡도: O(N) — 위 구현은 거리와 가격을 저장

가격은 순서대로 읽으면서 계산하기 어렵다. 입력에서 거리 전체가 먼저, 가격 전체가 나중에 나오기 때문이다. 거리만 저장하고 가격을 읽는 즉시 이전 구간 비용을 계산하면 추가 공간을 O(N)에서 거리 array 하나로 줄일 수 있지만, asymptotic space는 여전히 O(N)이다.

구현 순서에서 자주 생기는 실수

현재 도시 가격을 반영하는 시점

i번째 도로는 i번째 도시에서 출발하므로 그 도시의 가격을 사용할 수 있다. 비용을 더하기 전에 최솟값을 갱신한다.

minimumPrice = Math.min(minimumPrice, prices[i]);
totalCost += minimumPrice * distances[i];

첫 값으로 minimumPrice = prices[0]을 잡았다면 두 줄의 순서를 바꿔도 특정 구현에서는 맞을 수 있지만, “이 도로를 지나기 전에 살 수 있는 가격”이라는 invariant를 그대로 코드에 표현하는 편이 검토하기 쉽다.

마지막 가격으로 도로를 계산하지 않기

loop 조건은 i < cityCount - 1이다. prices[cityCount - 1]은 읽지만 사용할 도로가 없다.

int 곱셈 뒤 long 대입하지 않기

// 두 값이 int라면 곱셈 단계에서 overflow 가능
long cost = intPrice * intDistance;

// operand 중 하나 이상을 long으로 만든다
long cost = (long) intPrice * intDistance;

위 풀이처럼 처음부터 long으로 읽으면 더 단순하다.

작은 입력으로 검증하는 방법

greedy 규칙은 증명이 핵심이지만, 구현 실수는 작은 완전탐색과 비교해 찾을 수 있다.

작은 거리와 가격만 만든 뒤 각 도시에서 살 수 있는 기름 양을 모두 시도하는 dynamic programming을 reference로 둔다. 그리고 greedy 결과와 모두 같은지 비교한다.

검증할 때 특히 다음 경우를 넣는다.

• 가격이 계속 내려가는 경우: 5, 4, 3, 2
• 가격이 계속 올라가는 경우: 1, 2, 3, 4
• 같은 최저 가격이 반복되는 경우: 3, 3, 5, 3
• 도시가 두 개뿐인 최소 입력
• 큰 거리와 큰 가격의 long 경계

greedy 알고리즘은 “지금 가장 싸 보이는 선택”이라고만 설명하면 불안하다. 이 문제에서는 아직 가지 않은 도시의 기름을 과거 도로에 쓸 수 없고, 연료통에 제한이 없다는 두 조건이 prefix minimum 선택을 가능하게 만든다. 조건이 바뀌어 연료통 용량이 제한되거나 길이 여러 갈래로 나뉜다면 같은 풀이를 그대로 적용할 수 없다.

참고 자료

• 백준 13305번 주유소
• Java Language Specification: Multiplication Operator