[백준] 13305. 주유소 (Java)

문제

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

13305번: 주유소

풀이

0. 문제 해석

 

처음 위치에선 주유를 무조건 해야하므로

처음 위치의 가격을 기준으로 놓고, 이후의 도시들의 가격을 순서대로 비교하여 기준점보다 싼 도시가 있을 때,

그 도시까지의 거리만큼만 주유하고 그 도시에 간다음, 그 도시를 기준점으로 정하고 다시 이 작업을 반복하면 최솟값을 구할 수 있다.

 

위 그림에서는

시작점의 기름값이 5, 그 다음 도시의 기름값이 2 이므로

그 다음 도시로 가기 위한 기름만 충전 ( 5 * 2 ) 후 다음 도시로 간다.

 

이제 기준점의 기름값이 2, 그 다음 도시의 기름값이 4 이므로

또 그 다음 도시의 기름값을 확인한다. 도시의 기름값이 1 이므로

그 도시로 가기 위한 기름을 충전 ( 2 * 4 ) 한다.

 

결과적으로 최소 비용은 18이 된다.

 

1. 전체 코드

// [백준] 13305. 주유소 (Java)
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[] dir = new long[n-1];
    	long[] cost = new long[n];
    	
    	// 거리 입력
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n - 1; i++) {
    		dir[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 = 0L;
    	long curCost = cost[0];
    	
    	for(int i = 0; i < n - 1; i++) {
    		
    		if(cost[i] < curCost) {
    			curCost = cost[i];
    		}
    		
    		sum += curCost * dir[i];
    	}
    	
    	System.out.println(sum);
    }
}