[BOJ] 13305. 주유소

문제 원본 : https://www.acmicpc.net/problem/13305

13305번: 주유소

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] dist = new int[n - 1];
        int[] price = new int[n];

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

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

        long ans = 0;
        int min = price[0], sum = 0;
        for (int i = 1; i < n; ++i) {
            sum += dist[i - 1];

            if (min > price[i]) {
                ans += (long) min * sum;
                min = price[i];
                sum = 0;
            }
        }

        ans += (long) min * sum;

        bw.write(String.valueOf(ans));

        bw.close();
        br.close();
    }
}

• 그리디 알고리즘
• 현재 도시보다 기름 가격이 낮은 도시가 나올 때까지는 현재 도시에서 기름을 넣는다.
• 마지막 도시의 기름 가격이 최솟값이 아니라면 마지막 도시까지의 비용을 더해주지 않으므로
• 반복문이 끝나고 더해준다.