백준 13305 주유소 [JAVA]

문제 해석

• 첫번째 줄에 도시(=N)의 개수를 입력 받는다.

• 두번째 줄은 가장 왼쪽도시부터 가장 오른쪽 도시까지 인접한 도시끼리의 거리에 필요한 기름의 양을 입력받는다.

• 세번째 줄은 가장 왼쪽도시부터 가장 오른쪽 도시까지의 각 도시의 기름 1리터당 비용을 입력받는다.

• 모두 입력 받았다면, 가장 왼쪽 도시 -> 가장 오른쪽 도시을 가기 위한 가장 최소의 비용을 구하면 된다.

• 일단, 최소의 비용을 구하려면 당연히 각 도시의 기름 가격이 적은 곳에서 주유하는게 이득일 것이다.

• 이것만 알고 가면 문제는 크게 어려움이 없다.

예시로 

도시의 개수 : 5
도시 -> 다른 도시의 거리 값 : 4 2 3 1 
각 도시의 기름 값 : 3 4 2 5 1 

이라고 한다면...

• 일단 처음 도시인 3에서는 출발을 해야하기 때문에 최소 거리 값(=4) 만큼은 기름을 사야한다.
• 근데, 두번째 도시(4)이 첫번째 도시(3)보다 기름 값이 비싸니까 두번째 도시(4) -> 세번째 도시(2) 까지 가는 거리만큼 더 사야한다.
• 그리고 세번째 도시(2)부터는 첫번째 도시(3)의 기름 값보다 저렴하므로 여기서 부턴 세번째 도시(2)의 기름 값으로 산다. (네번째 도시(5)보다도 저렴하므로 네번째 도시(5) -> 다섯번째 도시(1)까지의 거리만큼 더 산다.)
• 위의 과정을 그림으로 설명하자면 이런식으로 기름을 사야 최소 비용이 나온다. (여기서, 마지막 도시(1)에서는 더 갈 곳이 없으므로 비용계산이 필요없다)
  
• 그림과 같은 방식으로 코드로 표현하려면 그냥 이전 값과 현재 값을 비교해서 작은 값의 비용을 넣어 계산하면 된다. (생각보다 간단!)

  if(prevMin > currentValue){
        cost[i] = currentValue;
        prevMin = currentValue;
  }else{ 
     cost[i] = prevMin;
  }

• 위와 같은 식으로 비교해가며 배열의 값을 채워주면 이 문제는 끝난 거나 다름 없다.
• 이에 대한 설명은 코드에 주석으로 작성해 두었다.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine()); //도시의 개수

        int[] oil = new int[N-1]; //도시->다른 도시로 필요한 기름의 양
        int[] cost = new int[N];  //도시별 기름 값

        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < oil.length; i++){ //필요한 기름의 양 입력
           oil[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());

        int prevMin = Integer.MAX_VALUE; //전인덱스 기준으로 최솟값 저장하는 변수
        
        for(int i = 0; i < cost.length; i++){ //도시별 기름 값 입력
            int currentValue = Integer.parseInt(st.nextToken());

            if(prevMin > currentValue){ //이전 비용보다 현재 비용이 더 작을 경우 현재 비용으로 갱신
                cost[i] = currentValue;
                prevMin = currentValue;
            }else{ // 같거나 클 경우 
                cost[i] = prevMin; // 이전 비용을 그대로 사용
            }
        }

        br.close();

		// 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수 / 리터당 가격은 1 이상 1,000,000,000 이하의 자연수
        // 최종 비용은 이 두개를 곱해서 구하기 때문애 Integer 범위를 넘기게 된다.
        // => long을 사용하는 이유
        long result = 0; //결과(최소 비용) 

        for(int i = 0; i < N-1; i++){ 
            result += ((long) cost[i] *oil[i]);
        }

        System.out.println(result);

    }
}

결과

느낀 점

처음에는 가장 왼쪽인 지역(0)은 방문하고 가장 오른족인 지역(N) 방문하지 않으니까 0 ~ (N-1)에서 최솟 값을 구해서 0 ~ (최소값인 지역-1)만큼은 0번째의 지역의 값을 곱하고 그 후로부턴 최솟값인 지역의 값을 곱하자로 접근했다가 그렇게 되면 최솟값은 한개만 나오니까 중간에 0번째보다 작은 값인데 최솟값이 아닌 경우를 계산하지 못해 최솟값이 나오지 않았다... 그래서 처음에 접근에서 시간을 썼는데 그때그때의 최솟값을 갱신해가면 되겠다는 생각이 나서 배열을 저장할때 내림차순으로 저장될 수 있게끔 바꿨더니 금방 풀 수 있었다.