실버3 난이도의 그리디로 분류되어 있는 문제였다.
DFS/BFS를 공부하고 있어서 그래프 이론 분류의 문제를 풀며 공부 중이었는데 잘못 눌러서 들어갔고, 문제를 읽어보고 이상하다 싶었는데 그리디 분류에 들어갔던 것이다.😅

첫 시도

처음 본 건데, 서브태스크라는 항목이 있어서 정답을 출력하더라도 조건이 맞지 않으면 부분점수만 부여하는 형식이었다. 첫번째 풀이는 서브태스크를 신경 쓰지 않고 정답 출력에만 중점을 둬서 풀이했다.

첫번째 주유소의 기름값을 최소값으로 놓고, 반복문을 돌면서 더 저렴한 기름값이 나오면 MIN 변수를 초기화 시켜주었다. 그리고 현재 위치의 주유소의 기름값이 MIN보다 작거나 같으면 현재 주유소의 기름값과 다음 주유소까지 거리를 곱하여 cost에 더해주었다.
현재 주유소의 기름값이 MIN보다 크면, MIN과 다음 주유소까지 거리를 곱하여 cost에 더하였다.

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

public class Main {

    public static int N;
    public static int cost;
    public static int MIN;
    public static int[] road;
    public static int[] oil;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        road = new int[N - 1];
        oil = new int[N];

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

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

        MIN = oil[0];

        for (int i = 0; i < N-1; i++) {
            if (i == 0) {
                cost += oil[0] * road[0];
            } else {
                if (oil[i] <= MIN) {
                    MIN = oil[i];
                    cost += oil[i] * road[i];
                } else {
                    cost += MIN * road[i];
                }
            }

        }

        System.out.println(cost);

    }
}

이 풀이는 채점결과가 58점인 걸 보아 조건 1, 2만 만족한 것이고 이는 로직만 맞았다는 뜻이다.
3번 조건은 큰 수의 연산을 처리할 수 있는지를 확인하는 것이다.
주어진 조건의 입력값이 10억 이하의 자연수였고 이는 곱하고 더할 경우 int의 범위를 넘아갔다.
따라서 int형이 아닌 long을 썼어야한다.

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

public class Main {

    public static int N;
    public static long cost;
    public static long MIN;
    public static long[] road;
    public static long[] oil;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        road = new long[N - 1];
        oil = new long[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < road.length; i++) {
            road[i] =  Long.parseLong(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < oil.length; i++) {
            oil[i] =  Long.parseLong(st.nextToken());
        }

        MIN = oil[0];

        for (int i = 0; i < N-1; i++) {
            if (i == 0) {
                cost += oil[0] * road[0];
            } else {
                if (oil[i] <= MIN) {
                    MIN = oil[i];
                    cost += oil[i] * road[i];
                } else {
                    cost += MIN * road[i];
                }
            }

        }

        System.out.println(cost);

    }
}

int를 long 타입으로 바꿔주니 바로 100점이 나왔다.

아직 코테 준비 초기라서 코드가 좀 지저분한 거 같아서 다른 분들의 코드를 좀 찾아보았다.
사실 그렇게 어려운 문제가 아니고, 복잡한 로직이 없기 때문에 크게 다른 점은 없었고 반복문쪽에 쓸모 없는 코드를 줄일 수 있었다.

for (int i = 0; i < N-1; i++) {
            MIN = Math.min(MIN,oil[i]);
            cost+=MIN*road[i];
        }