[BaekJoon] 13305번 - 주유소 [Java][C++]

문제 링크

---

1. 문제 풀이

맨 왼쪽 도시부터 오른쪽 도시까지 이동할 때 최소 비용을 구하는 문제로 그리디 알고리즘을 활용하면 해결할 수 있다.

현재 도시에서 다음 도시로 가는 거리에 대해 현재까지 지나온 도시 중 기름 값이 가장 쌌던 도시에서 기름을 채워서 가면 최소 비용으로 맨 오른쪽 도시까지 갈 수 있다.(기름통의 크기가 무제한이므로)

예제 입력 1의 경우 아래와 같이 나타낼 수 있다.

첫 번째 도시에서 두 번째 도시로 가는 거리 $2$ 를 위한 기름은 첫 번째 도시에서 채워야한다.

두 번째 도시에서 세 번째 도시로 가는 거리 $3$ 을 위한 기름은 첫 번째 도시보다 두 번째 도시에서 채우는 게 더 싸므로 두 번째 도시에서 채우면 된다.

세 번째 도시에서 네 번째 도시로 가는 거리 $1$ 을 위한 기름은 첫 번째 도시나 세 번째 도시보다 두 번째 도시에서 채우는 게 더 싸므로 두 번째 도시에서 채우면 된다.

첫 번째 도시에서 $2$ 의 기름을, 두 번째 도시에서 $4$ 의 기름을 채웠으므로 $5 \times 2 + 2 \times 4 = 18$ 이 최소 비용이다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

    static int MAX_PRICE = 1_000_000_000;

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

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

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

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

        long minPrice = MAX_PRICE;
        long sum = 0;
        for (int i = 0; i < N - 1; i++) {
            minPrice = Math.min(minPrice, price[i]);
            sum += minPrice * dist[i];
        }

        System.out.println(sum);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_PRICE = 1000000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> dist(n - 1);
    for (int& x : dist) cin >> x;

    vector<long long> price(n);
    for (long long& x : price) cin >> x;

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

    cout << sum;
}

---