[Baekjoon] 1446 지름길

설명

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

예시 입력

예시 출력

JavaScript
복사

JavaScript
복사

풀이 과정

우선 문제의 핵심 점화식을 말로서 풀어보겠습니다.

지름길을 통해 도착하는 위치는 지름길을 통과하지 않았을 때의 경우와 현재 위치에서 지름길을 통과했을 때의 경우 중 더 적은 비용이다.

최종 코드

package baekjoon.graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _1446 {

    static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            } else {
                return o1[0] - o2[0];
            }
        }
    });

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());

        int[] dist = new int[10001];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken()); // 출발 위치
            int A = Integer.parseInt(st.nextToken()); // 도착 위치
            int W = Integer.parseInt(st.nextToken()); // 지름길의 길이

            if (A > D) {
                continue; // 도착 위치가 도로의 길이를 넘어서는 경우
            }
            if (A - S < W) {
                continue; // 지름길이 아닌 경우
            }
            pq.add(new int[]{S, A, W});
        }

        int curr = 0;
        while (true) {
            if (curr == D) {
                break;
            }
            while (!pq.isEmpty()) {
                if (curr == pq.peek()[0]) {
                    dist[pq.peek()[1]] = Math.min(dist[pq.peek()[1]], dist[curr] + pq.peek()[2]);
                    pq.poll();
                } else {
                    dist[curr + 1] = Math.min(dist[curr + 1], dist[curr] + 1);
                    curr++;
                }
            }
            dist[curr + 1] = Math.min(dist[curr + 1], dist[curr] + 1);
            curr++;
        }
        System.out.print(dist[D]);
    }
}
JavaScript
복사