[백준/1446] 지름길 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버1
출처 : 백준 - 지름길

🦧 문제 풀이 접근

DP로 문제를 해결한다.
모든 지름길 데이터를 배열에 저장한다.
그후 DP배열을 0부터 D킬로미터까지 값을 넣어준다.

이때 지름길 도착위치와 일치하는 킬로미터에서
(이전칸 값+1, 시작위치 값 +지름길 길이) 중 작을 값을 대입한다.

DP의 D번째 칸까지 반복한다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    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 load [][] = new int[N][3];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<3;j++) {
                load[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int dp[] = new int[D+1];
        dp[0] = 0;
        for(int i=1;i<=D;i++) {
            dp[i] = dp[i-1]+1;
            for(int j=0;j<N;j++) {
                if(load[j][1] == i)
                    dp[i] = Math.min(dp[i],dp[load[j][0]]+load[j][2]);
            }
        }
        System.out.println(dp[D]);
    }
}

🥇 결과

🎓 느낀점

DP알고리즘으로 문제를 해결했는데 지름길 데이터를 계속해서 이중포문으로 반복하는 부분이 마음에 들지 않았다. 조금 더 효율적인 방법이 있을 것 같다.