[백준]JAVA - 13305번: 주유소

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

13305번: 주유소

풀이

문제 설명이 매우 길어서 어렵게 느껴지지만 생각보다 쉬운 문제이다.

N개의 도시와 N-1개의 도로가 있다. 그리고 도시에는 리터당 가격이 적혀있고 1리터당 1km를 갈 수 있다.

 

최소한의 비용으로 도시 A부터 D까지 가려면 어떻게 해야 될까? 바로 리터당 가격이 저렴한 기름을 넣는 것이다.

 

예제를 한 번 풀어보겠다.

첫 번째 도시에서 두 번째 도시로 가려면 5원짜리 기름을 2L 넣어야한다. 10원 적립.

 

두 번째 도시에서 세 번째 도시로 가려면 어떻게 할까?

첫 번째 도시의 기름값과 두 번째 도시의 기름값을 비교해봐야한다. 현재 첫 번째 도시보다 두 번째 도시의 기름값이 저렴하기 때문에 두 번째 도시에서 기름을 넣으면 된다.

10원 + 2원 * 3L이다. 세 번째 도시에 도착했을 때 16원 적립.

 

마지막 도시에서는 세 번째 도시의 기름값이 더 저렴하기 때문에 세 번째 도시에서 마지막 도시까지 갈 수 있는 기름을 넣으면 된다. 즉, 2원 * 4L가 된다.

 

총합은 18원이다.

 

위의 예제를 풀면서 느끼신 분도 계시겠지만 리터당 기름값이 내림차순일 경우에 주유하면 된다.

사실 처음에는 생각을 잘 못해서 바로 전 도시의 기름값만 비교했다.

for (int i=1; i<cnt-1; i++) {
    sum += Math.min(cost[i] * dist[i], cost[i-1] * dist[i]);
}

이렇게 하면 17점이 나온다. 왜냐하면 바로 전 도시의 기름값만 비교 후에 더 적은 값을 더했기 때문이다. 그냥 내 실수지만 위와 같이 푸는 사람이 있을수도 있지않을까? 해서 올려본다...

 

참고로 두 번째 서브태스크부턴 리터 당 가격과 거리가 최대 10,000으로 늘어난다. 그렇기 때문에 거리와 리터 당 기름, 합계 값을 int 형으로 하면 에러가 발생할 수 있다. long 형으로 선언해야한다.

 

<최종코드>

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 cnt = Integer.parseInt(br.readLine());
        long[] dist = new long[cnt-1];
        long[] cost = new long[cnt];
		
        // 거리 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i=0; i<cnt-1; i++) {
            dist[i] = Integer.parseInt(st.nextToken());
        }
		
        // 기름값 입력
        st = new StringTokenizer(br.readLine(), " ");
        for (int i=0; i<cnt; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }
        
        // 두 번째 도시는 고정값
        long sum = cost[0] * dist[0];
        long minCost = cost[0];
        
        for (int i=1; i<cnt-1; i++) {
            // 다음 도시에서 기름값이 낮아질 경우 기름값 변경
            if (minCost > cost[i]) minCost = cost[i];
            
            sum += minCost * dist[i];
        }
		
        System.out.println(sum);
    }	
}