[백준] 13305번 : 주유소

주유소

---

풀이 방법

처음에 접근을 잘못해서 10분 날려먹은 문제다..
리터당 주유 비용의 최소값을 찾아서 이후 나오는 모든 경로에 대해 적용해주면 된다고 생각했다.

주어진 예제만 보고 다른 상황은 고려하지 못했었다.
가령

6
10 10 10 10 10
2 3 4 5 1 10

처럼 2 -> 5 까지 가는 길에는 2의 비용으로 모든 기름을 사야하고, 나머지는 1의 비용으로 사야하는데,
최솟값만 생각해서 처리해버리면, 2 -> 5 까지 가는길을 처리해주지 못한 문제였다.

기업 코딩테스트 문제에서도 모든 반례가 나오지 않을건데, 여러 문제를 계속 풀면서 반례에 대해서도 생각하는 시간을 가져야겠다.

여튼 풀이 방법은 간단하다

가격을 비교해주면서, 저장한 최소 가격보다 낮은값이 나오면 바꿔주면서 계산하면 된다.

알고리즘 분류가 그리디알고리즘으로 구분되어있던데,
그리디알고리즘은 사실 조금만 논리적으로 생각하면 어렵지않게 해결 가능한 문제인 것 같다.

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine()); // 도시의 수
        long[] roads = new long[n-1]; // 도로의 길이
        long[] prices = new long[n-1]; // 주유소의 리터당 가격
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n-1;i++) {
            int road = Integer.parseInt(st.nextToken());
            roads[i] = road;
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) {
            int price = Integer.parseInt(st.nextToken());
            if(i==n-1) continue; // 마지막값은 사용하지 않음.
            prices[i] = price;
        }

        long result = 0;
        long minPrice = prices[0];
        result += minPrice * roads[0];
        for(int i=1;i<n-1;i++) {
            if(minPrice > prices[i])
                minPrice = prices[i];

            result += minPrice * roads[i];
        }

        System.out.println(result);

    }
}