백준[자바 java] 1446번 : 지름길

https://www.acmicpc.net/problem/1446

1446번: 지름길

 

문제설명

 

D킬로미터를 가야하는 세진이가 운전해야하는 거리의 최솟값을 구하는 문제이다.

 

풀이설명

다이나믹 프로그래밍을 사용하여 문제를 푼다.

지름길의 갯수만큼 배열을 만들어 거기에 지름길들을 입력받는다(arr)

dp배열을 D만큼 만들고 배열에 각각의 수를 넣어준다(지름길이 없을 때의  운전해야하는 거리)

 

dp에는 각각의 거리에 도달할 때 운전해야 하는 최솟값을 넣어준다.

우선 현재 위치보다 한칸 앞의 dp값에 1을 더한 값을 넣어준다.

그 다음, 지름길을 통해 현 위치에 도달 할 수 있는 경우들을 찾고 대입하는 과정을 거친다.

지름길 배열의 두번째 값이 현 위치와 동일하면 해당 지름길의 시작부분에 지름길을 더한 값을 구하고, 이를 현 dp값과 비교한 후 대입한다.(지름길의 길이가 지름길을 사용하지 않고 올 때보다 짧을 수 있기 때문에)

 

이 과정을 D까지 반복하면 dp[D]에는 저절로 최솟값이 들어가게 된다.

 

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


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 m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][3];

        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j<3;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[] dp = new int[m+1];

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

        for(int i = 1;i<=m;i++){

            dp[i] = Math.min(dp[i], dp[i-1] +1);
            for(int j = 0;j<n;j++){
                if(arr[j][1] == i){
                    dp[i] = Math.min(dp[i], dp[arr[j][0]] + arr[j][2]);
                }
            }
        }

//        for(int i = 0;i<=m;i++){
//            System.out.printf("%d ", dp[i]);
//        }

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

    }
}