[BOJ] 13305. 주유소 (🥈, 그리디)

🔗

풀이

주유소 최대 개수를 생각하면 완전 탐색은 불가능하고, 그래서 처음엔 뒤에서 앞으로 오면서 이전의 값을 저장해두는 dp 방식을 생각했지만 너무 복잡해졌다.

다시 앞에서 뒤로 가는 걸 생각하니 그냥 이전의 주유소 리터 값과 현재의 주유소 리터값을 비교해서 이전 값이 더 작으면 더 작은 걸로 업데이트하고, 현재 주유소 리터값이 더 작으면 그대로 가는 식으로 계산하면 되는 것 같았다. 주유소 리터값을 업데이트하면서 동시에 이동해야 하는 거리 * 리터 값을 최종 가격인 cost 에 추가해주면 된다.

// 주유소

package Baekjoon.Silver;

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

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

        long cost = 0;
        for (int i = 0; i < N-1; i++) {
            cost += LITER[i] * DISTANCE[i];
            if (LITER[i+1] > LITER[i]) {
                LITER[i+1] = LITER[i];
            }
        }

        System.out.println(cost);
    }
}`