[BOJ_13305] 주유소

설명

---

이전의 상태 값을 기억하고 최소한의 값으로 지속적인 탐색을 통해서 값을 구했습니다. O(N)이 걸렸고 정답 값이 오버플로우가 나기 때문에 long으로 설정하는 것이 중요했습니다.

코드

---

package BOJ.greedy;

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

public class BOJ_13305 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int N = Integer.parseInt(tk.nextToken());

        int[] dist = new int[N - 1];
        tk = new StringTokenizer(in.readLine()," ");
        for (int i = 0; i < N - 1; i++){
            dist[i] = Integer.parseInt(tk.nextToken());
        }
        int[] arr = new int[N];
        tk = new StringTokenizer(in.readLine()," ");
        for (int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(tk.nextToken());
        }
        int min = arr[0];
        long ans = 0;
        for (int i = 0; i < N - 1; i++){
            if(arr[i] >= min){
                ans += (long) dist[i] * min;
            }else{
                min = arr[i];
                ans += (long) dist[i] * min;
            }
        }
        System.out.println(ans);
    }
}

 

13305번: 주유소