[BOJ] 13305. 주유소

 

문제 소개

 

 

 

 

 

문제 요약

 

• N개의 도시
• 인접한 두 도시 사이의 도로의 개수 N-1개
• 도로 이동 시 1km마다 1L의 기름을 사용
• 처음 출발 시 기름이 없으므로 첫번째 도시에서 기름을 넣고 출발해야 함
• 도시 당 하나의 주유소가 위치해있음 (리터당 가격이 다름)

 

왼쪽 도시에서 오른쪽 도시로 이동하는 데에 드는 최소 주유비용을 구하는 과정을 정리해보았다.

 

 

 

가격이 싼 도시의 주유소에서 많이 넣는 것이 주유비를 최소화할 수 있는 방법이나, 처음 출발 시에는 기름이 없으므로 무조건 첫 번째 도시에서 주유를 하고 가야한다. 다음 도시의 주유소를 이용하는 것이 불가하기 때문에 현재 선택지에서 최선의 선택을 하는 Greedy 알고리즘을 적용하는 것이 하나의 방법이 될 수 있는 것으로 보인다.

 

 

 

 

풀이

 

import java.util.Scanner;

import static java.lang.Math.min;

public class Main {
 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] distances = new int[n-1];
        int[] costs = new int[n];

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

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

        int total_min_cost = 0;
        // 최소 비용 초기화
        int min_cost = costs[0];

        for (int i=0; i<distances.length; i++) {
            // 현재까지의 최소 주유비 갱신 (현재 주유소가 이전 주유소보다 쌀 경우 최소비용 갱신)
            min_cost = min(min_cost, costs[i]);
            // 최소 주유비로 이동하는 비용 계산
            total_min_cost += (min_cost * distances[i]);
        }

        System.out.println(total_min_cost);
    }
}

 

 

테스트케이스에 맞춰 풀이를 했으나 아래와 같이 58점이 나왔다. 58점이라면 문제에서 제시된 서브태스크 중에서 3번을 충족시키지 못했다는 것인데 이에 대해 자세히 알아보기로 했다.

 

 

 

 

문제 해결

 

일단 제약 조건이 있는 입력 정보를 다시 보기로 하였다. 입력 제약 조건에서 도시의 개수를 나타내는 정수는 2부터 100,000 이하로 주어지고, 첫 번째 도시부터 마지막 도시까지의 거리와 리터당 가격으로 들어올 수 있는 수가 10억이하로 상당히 큰 수가 들어올 수도 있음을 알 수 있다. 

 

 

예를 들어 기름의 리터당 가격이 1,000,000,000원이고 전체 도로의 길이가 1,000,000,000km일 경우, 총 주유비를 계산해보면 1,000,000,000 * 1,000,000,000 = 1,000,000,000,000,000,000 이라는 수가 나오게 된다.

 

여기서 알 수 있는 사실은 위의 수가 int 자료형의 정수 표현 범위(-2,147,483,648 ~ 2,147,483,647)를 크게 넘긴다는 것이다. 이러한 오버플로우를 방지하기 위해 정수 표현의 범위가 더 큰 자료형을 써야 하는데, -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 범위의 정수를 표현할 수 있는 long 자료형이 적합할 것으로 보인다.

 

	int 자료형(4바이트)	long 자료형(8바이트)
정수 표현 범위	-2,147,483,648 ~ 2,147,483,647	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

 

 

 

import java.util.Scanner;

import static java.lang.Math.min;

public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] distances = new long[n-1];
        long[] costs = new long[n];

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

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

        long total_min_cost = 0;
        // 최소 비용 초기화
        long min_cost = costs[0];


        for (int i=0; i<n-1; i++) {
            // 현재까지의 최소 주유비 갱신 (현재 주유소가 이전 주유소보다 쌀 경우 최소비용 갱신)

            if (min_cost > costs[i])
                min_cost = costs[i];

            System.out.println("min:" + min_cost + " " + costs[i]  + " " + distances[i]);
            // 최소 주유비로 이동하는 비용 계산
            total_min_cost += (min_cost * distances[i]);
        }

        System.out.println(total_min_cost);
    }
}