[BOJ 13305] 주유소 (Java)

문제

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

13305번: 주유소

도시 별 거리와 기름값

풀이

Greedy알고리즘을 사용해 풀 수 있는 문제이다.

무조건 싼 기름을 채워넣으면 해결할 수있다. 

 

1번 도시 -> 2번도시

1번 도시의 1리터 당 주유비용은 5원이며 1번과 2번도시 간 거리는 2이다. 

1번 도시에서는 무조건 주유를 해야 한다. 

총비용 = 5*2 = 10

 

2번 도시 -> 3번 도시

2번 도시에서 3번 도시로 가기 위해 기름을 주유해야 하는데 

1번 도시에서 미리 주유하는 것보다 2번 도시에서 주유하는것이 더 싸다. 

총 비용 += 10 + 2*3 = 16

 

3번 도시 -> 4번 도시

3번 도시의 기름값은 4원이다. 

2번 도시에서 미리 주유를 했다면 2원에 갈 수 있다. 

3번 도시에서 기름을 주유하지 않는 것이 유리하다. 

총 비용 += 16 + 2*1 = 18

 

결국 비용에 따라 이전 비용보다 값이 큰 경우에는 이전 비용으로 치환하면서 

거리를 곱해주면 답을 구할 수 있다.

AS-IS: 5 -> 2 -> 4

TO-BE: 5 -> 2 -> 2 

 

다른 예)

아래와 같이 비용을 치환한 후 거리를 곱해주면 된다.

5 -> 8 -> 3 -> 1 -> 3

5 -> 5 -> 3 -> 1 -> 1

 

참고로 정답이 int를 넘어가니 long형을 써야한다.

소스코드

package greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ13305 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cityCnt = Integer.parseInt(br.readLine());
        long[] dist = new long[cityCnt-1];
        long[] costs = new long[cityCnt-1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < dist.length; i++){
            dist[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < costs.length; i++){
            costs[i] = Integer.parseInt(st.nextToken());
        }

        long totalCost = 0;
        long prev = 0;
        for(int i = 0; i < costs.length; i++){
            if(i != 0 && prev < costs[i]){
                costs[i] = prev;
            }
            totalCost += costs[i]*dist[i];
            prev = costs[i];
        }
        System.out.println(totalCost);
    }
}