[백준] 지름길 (자바풀이)

문제

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

 

풀이과정

dp를 이용해 해결했습니다.

 

1. dp배열을 만든다 (현재위치까지 오는데 얼마나 운전을 했는지 저장하는 용도)

 

2. dp배열에 정상적으로 갈경우 운전거리를 미리 세팅해준다.

 

3. 정상적으로 현재 위치에 도착하는 경우와, (지름길 시작한 곳 + 지름길의 길이를 비교해)

dp배열에 저장해준다.

 

문제풀이

import java.util.*;

public class Main {
    static int n;
    static int d;
    static ArrayList<int[]> arr = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        d = in.nextInt();
        for(int i = 0; i < n; i++) {
            int start = in.nextInt();
            int end = in.nextInt();
            int ren = in.nextInt();
            arr.add(new int[] {start, end, ren});
        }

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

        for(int i = 1; i <= d; i++) {
            dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            for(int j = 0; j < n; j++) {
                int[]tmp = arr.get(j);
                dp[tmp[1]] = Math.min(dp[tmp[1]] , dp[tmp[0]] + tmp[2]);
            }
        }
        System.out.println(dp[d]);
    }
}