문제

이해

기름이 없는 자동차가 목적지까지 도달하려 한다. 제일 왼쪽 도시에서 출발해 목적지는 제일 오른쪽 도시이다.

각 도시에서는 주유를 할 수 있고 도시마다 1리터당 가격은 다르다.

그림과 같이 각 도시의 기름 가격과 거리가 주어질 때 목적지에 도달할 수 있는 가장 최소 금액을 구해야 한다.

단, 출발시에 기름은 없으며 기름을 넣을 수 있는 용량은 무제한이다.

접근

단순한 그리디 알고리즘으로 풀 수 있다. 왼쪽의 도시부터 차례로 읽으면서 만일 이전에 넣었던 도시의 기름 가격보다 현재 위치의 도시가 더 값싸다면 현재 도시에서 기름을 다시 채우는걸로 선택하면 된다.

다시 말해, 더 싼 가격을 찾으면 이전 도시에서 그곳에 도달하기 위한 기름만을 충전하면 된다.

위 조건은 항상 기름의 최솟값을 계산하게 된다.

단, 서브테스크의 조건을 보면 도시의 거리, 리터 당 가격이 1,000,000,000까지 넓혀지는데 최악의 경우에는 1,000,000,000 * 1,000,000,000을 계산하게 된다.

이는 기존의 정수형 long형을 초과하기 때문에 커버하기 위해서 BigInteger형을 사용해야 한다.

해당 객체는 기존 사칙연산과 다소 다르기 때문에 유의하여 코드를 작성해야 한다.

코드

package java_baekjoon;

import java.util.*;
import java.math.*;

public class prob13305 {
    static int[] price;
    static int[] distance;

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

        int N = sc.nextInt();

        price = new int[N];
        distance = new int[N - 1];

        for (int i = 0; i < N - 1; i++) {
            distance[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            price[i] = sc.nextInt();
        }

        int cur_min = Integer.MAX_VALUE;
        BigInteger sum = new BigInteger("0");

        for (int i = 0; i < N - 1; i++) {
            BigInteger price_B = new BigInteger(Integer.toString(price[i]));
            BigInteger distance_B = new BigInteger(Integer.toString(distance[i]));
            BigInteger cur_min_B = new BigInteger(Integer.toString(cur_min));

            if (price[i] < cur_min) {
                sum = sum.add(distance_B.multiply(price_B));
                cur_min = price[i];
            } else {
                sum = sum.add(distance_B.multiply(cur_min_B));
            }
        }

        System.out.println(sum);
    }
}

결과