[Java] 백준 13305 주유소

문제

https://www.acmicpc.net/problem/13305

13305번: 주유소

풀이

자 단순하게 O(N) 탐색으로 풀수있다. 쭈루룩 훑어가면서 현재 min 보다 낮은게 나오면 min을 업데이트 해주고 

거리 x min 누적합을 구해주면 OK.

 

참고

 

자바의 long type을 명시 안하면 int overflow 발생함으로 주의

로직이 틀렸나? 싶었는데 문제 조건의 변수 최댓값을 보니 역시나 자료형 이슈!

코드

import java.io.*;
import java.util.*;
public class Main {
    int n, k;
    int dist[],cost[];
    public static void main(String args[]) throws IOException {
        Main m = new Main();
        m.sol();
    }
    public long getN(){
        long ret = 0;
        long minN = -1;

        for(int i =0 ;i < dist.length ;i++){
            if(minN == -1 || minN > cost[i]){
                minN = cost[i];
            }
                ret += minN*dist[i];
        }
        return ret;
    }
    public void sol() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n= Integer.parseInt(br.readLine());
        dist = new int[n-1];
        cost = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i =0; i< n-1;i++) {
                dist[i] = Integer.parseInt(st.nextToken());
            }
        st = new StringTokenizer(br.readLine());
            for(int i =0 ; i< n;i++){
                cost[i] = Integer.parseInt(st.nextToken());
            }
        System.out.println(getN());
    }
}