[JAVA] 백준 1446 - 지름길

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

 

 

 

점화식을 세울 수 있다.

dp는 나름대로 노하우가 생겼는데

1) dp배열이 의미하는것이 무엇인지를 명확히 세우는것이 중요하고,

2) 항상 i 와 i + 1의 관계를 생각하면 잘 떠오르는것같다. 최대한 다른것들은 배제하고, 컴팩트하게 i 와 i + 1의 관계만을 생각하면 된다.

 

 

제일 중요한것은 dp[i]가 무엇인지 정의를 해야한다, dp[i]란 i까지 도착하는데 걸리는 최솟길이 라고 정의했다.

 

그다음 점화식을 세워야 한다. 최대한 i 와 i + 1 관계 외에 다른 복잡한 생각을 지웠더니 은근히 잘 떠오를 수 있었다.

점화식

1) (도착점이 i인 지름길이 존재할 때) ->  dp[i] = min(dp[i] , dp[지름길의 시작점] + 지름길의 길이)

2) (지름길이 없을때)  ->dp[i] = dp[i - 1];

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    static int N;
    static int D;
    static int[] dp;
    static ArrayList<Shortcut> list = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().split(" ");
        N = Integer.parseInt(lines[0]);
        D = Integer.parseInt(lines[1]);
        dp = new int[D + 1];
        for (int i = 0; i <= D; i++) {
            dp[i] = i;
        }
        for (int i = 0; i < N; i++) {
            lines = br.readLine().split(" ");

            int start = Integer.parseInt(lines[0]);
            int end = Integer.parseInt(lines[1]);
            int length = Integer.parseInt(lines[2]);
            list.add(new Shortcut(start,end,length));
            
        }
        dp[0] = 0;
        dp[1] = 1;

        for(int i = 2 ; i <= D ; i++){
            dp[i] = dp[i - 1] + 1;
            for(Shortcut shortcut : list){
                if(shortcut.end == i){//지름길 존재
                    dp[i] = Math.min(dp[i], dp[i - (shortcut.end - shortcut.start)] + shortcut.length);
                }
            }
        }

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


    }


}
class Shortcut{
    int start;
    int end;
    int length;

    public Shortcut(int start , int end, int length){
        this.start = start;
        this.end = end;
        this.length = length;
    }
}