알고리즘[Greedy]_백준_13305

• 도로는 수평방향으로 일직선 상위에 있다.
• 인접한 도시간의 거리는 다를 수 있다.
• 가장 처음위치에서는 반드시 기름을 채워야 한다.
• 키로당 1리터의 거리 이동(연비똥이네,,,)
• 주유소는 도시마다 한 개이고, 기름 가격은 다르다.
• 기름가격이 싼 곳에서 적절히 기름을 구매해서 최종적으로 소요되는 기름의 가격을 최소화 시켜라
• 기름 가격이 가장 싼곳에서 최대한 많이 사야한다.
• 변수의 최댓값을 생각했을 때, int형이 아닌 Long형을 사용해야 한다.

다음과 같이 입력예제로 예를 들어보자. 

4

2 3 1

5 2 4 1

첫 번째 도시는 기름 가격이 5원으로 비싸지만, 기본적으로 이동해야 하기 때문에 최소한으로 삽니다. (5 * 2) = 10

두번째 도시는 기름가격이 저렴하기 때문에 구매하는데, 이때 다음 도시의 가격을 살펴봐야 합니다.(모든 도시의 기름값을 배열로 받아서 순회하여 현재 도시보다 저렴한 기름 값이 있는 도시가 나타날 때마다 그 도시의 기름값을 최소값을 저장장하는 변수에 갱신.)

결국 내림차순 즉, 이전에 산 기름 값보다 저렴한 가격으로만 구매해야 한다는 말입니다. 자세한 내용은 소스코드와 주석과 함께 살펴보시면 이해가 되겠습니다.

 

package Greedy;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _13305 {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        //도시의 개수 
        int N = Integer.parseInt(br.readLine());
        
        //도로의 길이 
        int []way = new int[N-1];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N-1;i++) {
            way[i] = Integer.parseInt(st.nextToken());
        }
        
        //기름의 가격 
        int []oil = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N;i++) {
            oil[i] = Integer.parseInt(st.nextToken());
        }
        //비싼곳에서는 필요한 만큼만, 싼곳에서 많이
        //처음도시에서는 반드시 주유를 해야한다. 
        //다음으로 도착한 도시보다 기름값이 싼 곳이 있다면 그 곳까지 갈 수 있는 기름만 구매
        //새로 도착한 곳에서 또 자신보다 기름값이 싼 곳이 있다면 그 곳까지 갈 수 있는 기름만 구매 
        //만약 위 과정을 진행하다가 더 이상 저렴한 가격이 없고 도착지점이 나온다면 그대로 꼴인
        
        /*
            N 4
            R 2 3 1
            O 5 2 4 1
        */
        
        
        int total_oil_price = 0;
        int min_oil_cost = oil[0];
        
        for(int i=0; i<oil.length-1;i++) {
            if(min_oil_cost > oil[i]) {//현재최소값보다 저렴한 기름값을 찾으면 현재 있는 곳에서 기름을 구매하여 그곳까지 이동해라 
                min_oil_cost = oil[i];
            }
            total_oil_price += min_oil_cost * way[i];
        }
        
        System.out.println(total_oil_price);
    }
 
}