문제 출처

단계별로 풀어보기 > 그리디 알고리즘 > 주유소
https://www.acmicpc.net/problem/13305

문제 설명

도시별 기름 값 N개와 도시 별 거리 N-1개가 주어진다.
기름을 충전할 때, 무한으로 충전할 수 있을 때, 가장 왼쪽 도시부터 가장 오른쪽 도시에 도착하는 최솟값을 return 하라.
단, 기름은 1km 가는데 1L가 사용된다.

접근 방법

마지막 도시의 경우 더 이상 가지 않아도 되므로, 마지막 도시의 기름 값은 사용되지 않는다. 를 유의하면서 풀면 된다.
처음 가장 최소 기름 값은 첫 도시의 기름 값으로 설정한다. 그 이유는 첫 도시에서는 기름이 0이기 때문에 무조건적으로 기름을 얻어야 하기 때문이다.
이후, 도시의 거리를 기록한 city 배열을 순회하면서 현재 최소 기름값과 도착한 도시의 기름 값을 비교하여 최소 기름값을 설정한다. 설정한 기름값을 통해 현재 도시로부터 다음 도시의 거리를 최소 기름값을 곱하는 것을 반복한다.
풀이과정은 최소 기름 값으로 최대한 멀리 가는 것이기 때문에 다음 도시의 기름 값보다 비싸면 이전 기름 값으로 미리 기름을 얻으면 되기 때문이다.

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

public class 주유소 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] city = new int[N-1];
        int[] charge = new int[N];


        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N-1; i++){
            city[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            charge[i] = Integer.parseInt(st.nextToken());
        }

        long totalCost = 0;
        int minPrice = charge[0];

        for(int i = 0; i<N-1; i++){
            if(charge[i] < minPrice){
                minPrice = charge[i];
            }
            totalCost += (long) minPrice * city[i];
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(totalCost));
        bw.flush();
        bw.close();
        br.close();
    }
}

Review

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

public class 주유소_review {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N-1; i++){
            distance[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            charge[i] = Integer.parseInt(st.nextToken());
        }

        int Min = charge[0];
        long sum = 0;

        for(int i = 0; i<N-1; i++){
            Min = Math.min(charge[i],Min);
            sum += (long) Min*distance[i];
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음에 푼 방식은 제일 싼 도시를 찾고, 그 도시로부터 오른쪽의 거리만큼 계산하는 방식을 택했다. 하지만 이는 가장 싼 도시가 있어도, 거기에서 뒤쪽 전체를 커버하는 게 최적이 아닐 수도 잇기 때문에 방법은 58점을 맞았다.

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

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());
        int[] city = new int[N-1];
        int[] charge = new int[N];


        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N-1; i++){
            city[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            charge[i] = Integer.parseInt(st.nextToken());
        }


        int idx = N-1;

        int sum = 0;
        // 제일 싼 도시 찾고, 해당 도시부터 오른쪽 끝까지 거리를 계산
        while(idx > 0){
            int Min = Integer.MAX_VALUE;
            int leastChargeCity = 0;
            for(int j = 0; j<idx; j++){
                if(Min > charge[j]){
                    Min = charge[j];
                    leastChargeCity = j;
                }
            }
            for(int k = leastChargeCity; k<idx; k++){
                sum += charge[leastChargeCity] * city[k];
            }
            idx = leastChargeCity;
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
        br.close();
    }
}

Review
일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.
와 같이 큰 수가 나올 때는 (long)으로 변환을 해주자

문제푼 흔적

Review