문제 요약 - N개의 도시가 일직선으로 이어져 있고, N-1개의 도로가 있다 - 각 도시에는 주유소가 있으며, 리터당 가격이 다르다 - 1km 이동 시 1리터의 기름이 소모된다 - 출발 도시에서 오른쪽 끝 도시까지의 최소 이동 비용을 구하는 문제

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long[] distance = new long[n - 1];
        long[] price = new long[n];

        for (int i = 0; i < n - 1; i++) {
            distance[i] = sc.nextLong();
        }

        for (int i = 0; i < n; i++) {
            price[i] = sc.nextLong();
        }

        long minPrice = price[0];
        long totalCost = 0;

        for (int i = 0; i < n - 1; i++) {
            // 이전까지의 최소 주유 가격으로 거리만큼 기름을 넣는다
            totalCost += minPrice * distance[i];

            // 현재 도시의 주유 가격이 더 싸면 그걸로 갱신
            if (price[i + 1] < minPrice) {
                minPrice = price[i + 1];
            }
        }

        System.out.println(totalCost);
    }
}

풀이 설명 이 문제는 그리디 알고리즘으로 풀었다. 핵심은 "앞으로 이동할 거리만큼의 기름을 언제 넣는 게 가장 저렴한가?"를 판단하는 것이다. 그런데 미래의 가격을 다 예측하지 않고도, 매 순간 지금까지 가장 저렴했던 가격으로 기름을 넣는다는 전략이면 충분했다. 예를 들어 현재 위치보다 다음 도시의 기름값이 비싸다면 지금 넣는 게 유리하고, 다음 도시가 더 싸면 그때 넣으면 되기 때문이다. 이렇게 생각해서 현재까지의 최솟값을 유지하며 그 가격으로 이동 거리만큼 기름값을 누적하는 방식으로 풀었다.