백준 지름길 1446 - JAVA

1. 문제

 

 

2. 접근

문제를 요약하면 고속도로 길이 D까지 최단으로 이동하는 거리 구하기이다. 일직선인 고속도로가 주어지고 중간 중간 지름길이 주어진다. 각 지름길의 결과가 이후의 거리에 영향을 주기 때문에 누적할 수 있는 DP를 이용하기로 했다. 

 

3. 풀이

1. 지름길의 End값을 갱신

`dp[end] = Min(dp[end], dp[statr] + cost)` 라는 점화식을 이용해서 지름길을 오름차순 정렬 후에 더 빨리 갈 수 있는 방법을 갱신하고자 했다. 이때 dp[i]는 i목적까지 가는 거리이다.

 

하지만 놓쳤던 것은 모든 dp값은 바로 직전의 값에 영향을 받는다는 것이었다. dp[i-1] +1의 값도 고려해서 이동한 거리 중 최소값을 구해야한다.

 

그래서 최종 점화식은 아래와 같다. 처음 dp[i]값을 dp[i-1]+1로 지정해주고 end로 향하는 지름길이 있으면 고려해서 갱신해주었다.

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

    for(int i=0; i<=D; i++){
        if(i != 0){
            dp[i] =  dp[i-1] +1;
        }
        for(Load load : loads){
            if(load.end == i){
                // 더 작은 값으로 갱신
                dp[load.end] = Math.min(dp[load.start] + load.dis, dp[load.end]);
            }
        }
    }
    System.out.println(dp[D]);
}

 

4. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   // 지름길의 개수
        int D = Integer.parseInt(st.nextToken());   // 지나야 할 고속도로 길이

        List<Load> loads = new ArrayList<>();
        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 cost = Integer.parseInt(st.nextToken());

            loads.add(new Load(start, end, cost));
        }
        
        int [] dp = new int[D+1];

        for(int i=0; i<=D; i++){
            if(i != 0){
                dp[i] =  dp[i-1] +1;
            }
            for(Load load : loads){
                if(load.end == i){
                    // 더 작은 값으로 갱신
                    dp[load.end] = Math.min(dp[load.start] + load.dis, dp[load.end]);
                }
            }
        }
        System.out.println(dp[D]);
    }
 }

 class Load {
    int start;
    int end;
    int dis;

     public Load(int start, int end, int dis) {
         this.start = start;
         this.end = end;
         this.dis = dis;
     }

 }