[JAVA][백준][13305]주유소

알고리즘

by 성찬우 2021. 9. 13. 23:01

13305 주유소 문제이다.

우선 다양한 조건들이 있는데 하나씩 뜯어보자.

1. 계산 방식

다양한 방법을 생각해 보았는데 우리가 알고리즘을 문제를 푸는 것에 있어서 절대적으로 먼저 생각해야하는 것이 있다.

컴퓨터는 우리랑 다르게 계획을 세우는 것을 모른다. 오로지 우리가 세워준 로직에 의존한다. 그렇기 때문에 우리가 진짜 주유소에 들리는 것이라면 제일 가격이 싼곳을 찾고 거리를 계산하여 문제를 해결하겠다만..

컴퓨터는 그때 그때 필요한 부분에서 계산이 가능하다.

우리는 그 부분을 캐치해서 필요한 수만 가져와서 사용하면 된다.

본론으로 들어가겠다.

우선 [0]번째 주유소의 가격이 중요하다. [0]번째의 주유소는 무조건 넣어야한다. 자동차는 우선 굴러가야할 것 아닌가?

[0]번째의 주유소는 우리가 가질수 있는 "최저가" 이다.

하지만

[1]번째를 만난 순간 다를수도있다.

( [0]의 가격 > [1]의 가격 ) 이라면?

당연히 [1]번째에서는 [1]가격을 넣어야한다.

( [1]의 가격 < [2]의 가격 ) 이라면?

[2]번째에 도달했지만 현재 최저가인 [1]의 가격을 넣어야한다.

즉, 우리가 몇번째 까지 왓던간에 그 전에 만낫던 주유소가 싼 가격이라면 그 가격으로 계산하면 된다.

~~물리적으로 생각하면 당연히 3번째 주유소인데 2번째 주유소 가격으로 계산을 못하겠지 하지만 이건 컴퓨터라니까..?!~~

2. 변수

2-1. 주유소 개수 [N]

2-2. 주유소 가격 [입력]

2-3. 주유소별 간격 개수 [N-1]

2-4. 주유소별 간격 [입력]

2-5. 총합 [sum]

2-6 최소 가격 [minCost]

총 6가지로 볼수 있다.

우선 주유소 개수를 정해주자 그러면 자연스럽게 가격과 간격이 정해지니까!

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        long[] dist = new long[N-1];     //거리 
        long[] cost = new long[N];       //가격

개인적으로 BufferedReader 가 편하다..

(대부분의 상황에서 Scanner보다 빠르다. 그냥 가져다 쓰는걸 추천 나중에 알아서 외워짐)

제한된 숫자 크기가 매우 크길래 long으로 선언해줌. [ int형의 범위 (–2,147,483,648 ~ 2,147,483,647) ]

당연히 갯수가 N 개면 사이 거리는 N-1개 겟쥬?

이제 [입력] 해줄 차례이다.

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

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

for 문을 돌려서 거리(dist)의 [i]번째를 입력하게 해주고.

가격(cost)의 [i]번째를 입력하게 하였다.

StringTokenizer의 경우는 split을 하는 기능인데 "(스페이스바)" 로 되어있습니다.

띄어쓰기로 해당 수들을 나누어 주었습니다.

3. 계산

        long sum = 0;
        long minCost = cost[0];

        for(int i=0; i<N-1; i++){
            if(cost[i]<minCost){
                minCost = cost[i];
            }

            sum += minCost*dist[i];
        }

        System.out.println(sum);

최종 계산을 내려줄 sum과 현재 까지의 최저가를 담을 변수 minCost이다.

for문을 돌면서 가격이 싼곳이 minCost로 대체되며 다음 거리와의 곱을 하여 그 구간의 가격을 sum에 넣어준다.

이동 간격 -----5>>> -----3>>> -----4>>> -----2>>>

5원

2원

3원

1원

4원

이동 간격 -----5>>> -----3>>> -----4>>> -----2>>>

실제 계산

5원

2원

3원 2원

1원

4원

해당 예시의 실제 계산은

5원 5번 ----> 2원 3번 ---->2원 4번 ----> 1원 2번 이므로

(5*5) + (2*3) + (2*4) + (1*2) 이 되겠다.

최종 코드

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[] dist = new long[N-1];
        long[] cost = new long[N];

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

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

        long sum = 0;
        long minCost = cost[0];

        for(int i=0; i<N-1; i++){
            if(cost[i]<minCost){
                minCost = cost[i];
            }

            sum += minCost*dist[i];
        }

        System.out.println(sum);
    }
}