[JAVA] 백준 13305 - 주유소

백준 13305 - 주유소

문제

---

알고리즘 (접근방법)

처음에 문제를 읽고 이해가 하나도 되지 않았다.
최소한으로 계산해보려고 거리들의 합을 가격으로 나누어 보기도하고 거리가 가격으로 나누어 떨어지는지 별 방법을 동원했지만, 정답은 주유 가격을 최소로 맞추면 되는 것이였다.
처음 도시는 주행을 해야하므로 무조건 다음 도시 거리 만큼 주유를 해야한다.
그런다음 첫 도시와 다음 도시의 주유 가격을 비교하여 더 낮은 주유 가격만큼 주유한다. 도시별로 주유 가격을 비교하면서 최소값으로 주유를 하면 된다.

결론은 최솟값을 계속 바꾸어 주면서 주유 하면 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());

        long[] km = new long[n - 1];
        long[] price = new long[n];

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

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

        long sum = 0;
        long min = price[0];

        for(int i=0; i<km.length; i++) {
            if(price[i] < min) {
                min = price[i];
            }
            sum += (min * km[i]);
        }

        System.out.println(sum);
    }
}

문제설명이 너무 길어 처음에는 너무 헷갈렸다.
결국 그리디 알고리즘이라는 틀에서 생각하면 최소를 생각하면 되었다.
너무 생각을 많이하여 어렵게 접근했던것 같다.