[Silver V][JAVA] 13305번:주유소

분류 : 그리디 알고리즘
난이도 : 실버3
링크 : https://www.acmicpc.net/problem/13305

1. 나중에 들를 도시중에 현재 도시보다 싼 곳을 찾기
   1-1. 그런 도시가 있다면, 해당 도시까지 필요한 연료만 구매
   1-2. 그런 도시가 없다면, 현재 도시에서 목적지까지 필요한 모든 연료 구매
   

알고리즘 (접근방법)
처음 도시는 주행을 해야하므로 무조건 다음 도시 거리 만큼 주유를 해야한다.
그런다음 첫 도시와 다음 도시의 주유 가격을 비교하여 더 낮은 주유 가격만큼 주유한다. 도시별로 주유 가격을 비교하면서 최소값으로 주유를 하면 된다.

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 주유소 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        long[] road = new long[N - 1];
        long[] fuel = new long[N];

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

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

        long sum = 0;
        long MIN = Integer.MAX_VALUE;

        for (int i = 0; i < N-1; i++) {
            MIN = Math.min(MIN, fuel[i]);
            sum += road[i] * MIN;
        }
        System.out.println(sum);
    }
}