[Baekjoon] 13305 - 주유소

📝 문제

 

 

🔑 풀이 과정

· 처음에는 어려워 보였으나, 생각해보면 쉬운 문제.

 

· 우리가 구해야 하는 것은 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용

즉, 현 시점에서 선택할 수 있는 리터당 가격 중 제일 싼 가격으로 주유를 하는 것

 

· 현재 주유 가격을 저장한 뒤 도시들을 이동하면서 리터당 가격이 더 싼 곳을 만나면, 그 가격으로 주유한다. 만나기 전까지는 저장된 가격으로 계속 주유한다. 이를 계속 반복한다.

 

· 처음 출발할 때 기름이 없으므로 0번 도시에서 1번 도시 이동할때는 무조건 0번 도시의 리터당 가격으로 주유를 해야한다.

 

· 각 도시의 리터당 가격은 N개 입력받으나 맨 마지막 도시는 도착하는 도시이므로 마지막으로 입력받는 리터당 가격은 쓸모가 없다. (현재 풀이에선 필요가 없음)

 

 

🔓 답안

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력
        int N = Integer.parseInt(br.readLine());
        int[] distance = new int[N-1];
        int[] price = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N-1; i++){
            distance[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            price[i] = Integer.parseInt(st.nextToken());
        }
        //입력 종료

        long total = (long)price[0] * distance[0]; //0번 도시에서 1번도시로 가는 가격은 무조건 고정이다. 처음 출발할 때는 기름이 없기 때문
        int leastPrice = price[0];
        for(int i = 1; i < N-1; i++){
            if(price[i] < leastPrice)  //현재 도착한 도시의 기름 가격이 싼지, 앞서 주유했던 기름 가격이 더 싼지 비교
                leastPrice = price[i];

            total += (long)leastPrice * distance[i];
        }

        bw.write(total + "\n");
        bw.flush();
        bw.close();

    }

}

 

 

 

🖤 알고리즘 분류

- 그리디 알고리즘