<BOJ>13305번: 주유소

문제

13305번: 주유소

접근

• N개의 도시, N-1개의 간선 및 거리, N개의 주유소 기름값
• 처음 이동 시 (첫 주유소 가격 * 첫 이동 거리)대로 주유하고 움직여야 함.
• 마지막 도시에 위치한 주유소의 기름 값은 사실상 의미가 없음(도착 후 주유할 필요가 없기 때문)
  
  위 조건을 고려해서 greedy한 방법으로 풀이하면 된다.

내 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] dist = new long[n-1];
        long[] cost = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n-1; i++) {
            dist[i] = Long.parseLong(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            cost[i] = Long.parseLong(st.nextToken());
        }
        long sum = 0;
        long tmp = cost[0];
        for (int i = 0; i < n-1; i++) {
            if (tmp > cost[i]) tmp = cost[i];
            sum += (tmp * dist[i]);
        }

        System.out.println(sum);
    }
}

입력 조건 상의 범위를 고려해서 int가 아닌 long으로 타입을 설정하자.
(문제를 제대로 읽고 넘어가야 함...)