문제 링크

풀이

dp[i] = 0 ~ i까지의 최소 거리로 정의

모든 위치 i에 대해 반복문을 돌며 아래의 상황을 고려한다.

• 일반 도로로 i+1에 이동하는 경우 → dp[i+1] = dp[i] + 1

• 현재 위치(i)에서 시작하는 지름길이 있다면 해당 지름길을 타고 end로 이동하는 경우 → dp[end] = min(dp[end], dp[i] + dist)

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol1446 {
    static int n, d;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        List<ShortCut> shortCuts = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            if (end - start < dist || end > d) {
                continue;
            }
            shortCuts.add(new ShortCut(start, end, dist));
        }
        Collections.sort(shortCuts);

        int[] dp = new int[d + 1];
        for (int i = 0; i <= d; i++) {
            dp[i] = i;
        }

        for (int i = 0; i <= d; i++) {
            if (i > 0) {
                dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            }
            for (ShortCut sc : shortCuts) {
                if (sc.start == i) {
                    if (dp[sc.end] > dp[i] + sc.dist) {
                        dp[sc.end] = dp[i] + sc.dist;
                    }
                }
            }
        }
        System.out.println(dp[d]);
    }

    public static class ShortCut implements Comparable<ShortCut> {
        int start, end, dist;

        ShortCut(int start, int end, int dist) {
            this.start = start;
            this.end = end;
            this.dist = dist;
        }

        @Override
        public int compareTo(ShortCut o) {
            if (this.start != o.start) {
                return Integer.compare(this.start, o.start);
            } else if (this.end != o.end) {
                return Integer.compare(this.end, o.end);
            } else {
                return Integer.compare(this.dist, o.dist);
            }
        }
    }
}