[JAVA]백준 13305번: 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

1. 문제 설명

 

문제

• N개의 각 도시를 연결하는 도로의 길이, 각 도시에 있는 주유소에 있는 기름 가격이 주어진다.
• 처음 출발할 때, 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다.
• 기름통의 크기는 무제한이다.
• 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다.
• 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 문제

조건

• 2 <=N <=100,000
• 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1 이상 1,000,000,000 이하의 자연수
• 주유소 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

 

2. 풀이

 

최소 비용으로 이동할 수 있는 방법은 제일 주유소 가격이 싼 곳에서 제일 오른쪽까지 이동할 수 있는 거리만큼 기름을 구매하는 것이다.

 

따라서, 오른쪽 도시로 이동해나가면서, 최소 기름값의 비용 * 다음 도시 이동 거리를 더해가면서 답을 구하면 된다.

 

주의해야 할 점은, int 형이 아닌 long형으로 구해야 한다는 것이다.

 

답의 최대 값은 제일 왼쪽 도시부터 오른쪽 도시까지의 거리 최댓값 * 기름 비용의 최댓값이다.

 

따라서 1,000,000,000,000,000,000의 값이 나오게 되고 이는 int 형의 범위를 벗어난다.

 

3. 코드

// JAVA 11 , 메모리 : 35512KB, 시간 : 384ms

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int cityNum = Integer.parseInt(br.readLine());
        long min = 1000000001;
        long answer = 0;

        int[] distance = new int[cityNum - 1];
        int[] fee = new int[cityNum];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int x = 0; x < cityNum - 1; x++) {
            distance[x] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());

        for (int x = 0; x < cityNum; x++) {
            fee[x] = Integer.parseInt(st.nextToken());
        }

        for (int x = 0; x < cityNum - 1; x++) {
            min = Math.min(min, fee[x]);

            answer += min * distance[x];
        }

        bw.write(String.valueOf(answer));
        bw.flush();


    }

}