[BOJ] 1446 - 지름길

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1446

1446번: 지름길

난이도: 골드 5

사용언어: JAVA

 

풀이

저는 이 문제를 다이나믹 프로그래밍을 이용해 해결했습니다. dp 배열을 생성하고, 해당 위치까지 올 수 있는 가장 짧은 거리의 값을 배열에 저장하였습니다.

 

특정 위치까지 올 수 있는 가장 짧은 거리는 현재 dp에 저장된 값과 한 칸 전까지 올 수 있는 가장 짧은 거리 +1, 그리고 해당 지점에 도착하는 지름길이 있을 경우에는 해당 지름길을 이용한 거리, 이 세 가지를 비교하여 가장 짧은 거리를 선택해주면 됩니다.

 

import java.io.*;
import java.util.*;
 
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 = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());
        int[][] arr = new int[N][3]; // 지름길의 정보를 저장하기 위한 배열
        int[] dp = new int[D + 1];
        int cnt = 0;
        int ptr = 1;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
       } // 지름길 정보 저장
 
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        Arrays.sort(arr, new Comparator<int[]>() { // 지름길 도착 지점을 기준으로 오름차순 정렬
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
 
        while (cnt < N) { // 지름길을 모두 확인할 때 까지
            if (arr[cnt][1] > D) { // 지름길의 도착지점이 D보다 크다면
                cnt++;
                continue; // 체크 x
            }
            while (ptr < arr[cnt][1]) { // 지름길의 도착지점까지
                dp[ptr] = Math.min(dp[ptr], dp[ptr - 1] + 1); dp 배열을 채워주고
                ptr++;
            }
            dp[ptr] = Math.min(dp[ptr], Math.min(dp[ptr - 1] + 1, dp[arr[cnt][0]] + arr[cnt][2])); // 도착지점의 dp도 작성
            cnt++;
        }
 
        while (ptr <= D) { // 지름길 확인이 끝나도 D에 다다르지 못한경우
            dp[ptr] = Math.min(dp[ptr], dp[ptr - 1] + 1); // dp배열을 채워줌
            ptr++;
        }
        
        bw.write(String.valueOf(dp[D]));
        bw.flush();
        bw.close();
        br.close();
    }
}