레벨업 일지

[Java] 백준 13305 주유소 본문

카테고리 없음

[Java] 백준 13305 주유소

24시간이모자란 2023. 1. 20. 00:28

문제

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

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

풀이

자 단순하게 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());
    }
}
저작자표시
Comments