[PS] BOJ1446 지름길 ( DP ) With JAVA

1446번: 지름길

 

 

◎ 문제풀이 

 

DP 발상이 가능하면 쉽게 풀 수 있는 문제이다.

 

 

 

 

 

어느 한 지점에 도착할 수 있는 경우는 2가지이다.

 

1) 바로 옆에서 1 이동하는 경우

2) 지름길로 이동하는 경우

 

지름길로 이동하는 경우는 여러가지가 될 수 있다. 그러므로 여러 가지 경우 중에서 가장 최소인 비용을 기억(메모리제이션) 해놓고 다음 지점의 최소비용 구할 때 사용하면 된다. 

 

0부터 목표지점 D까지 Bottom-Up 방식으로 1씩 dp 값을 구하는 방식으로 문제를 풀면 된다. 

 

◎ 코드

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


//BOJ1446 지름길
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[] dp = new int[d+1];
        HashMap<Integer, List<int[]>> map = new HashMap<>();


        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());

            List<int[]> shortCut = map.getOrDefault(end, new ArrayList<>());
            shortCut.add(new int[]{start, dist});
            map.put(end, shortCut);

        }

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

            if (map.containsKey(i)) {
                for (int[] shortCut : map.get(i)) {
                    minDist = Math.min(minDist, dp[shortCut[0]] + shortCut[1]);
                }
            }

            dp[i] = minDist;
        }

        System.out.println(dp[d]);

    }

}