99클럽 코테 스터디 27일차 TIL [DP]

- 오늘의 학습 키워드 : DP

[문제 이름 : 지름길 (백준, S1)]
문제 url : https://www.acmicpc.net/problem/1446

내가 작성한 코드는 아래와 같다.

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

public class Main {
    static int[][] graph;
    static int[] dp;
    static int n, d;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        graph = new int[n][3];

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

        // 모든 거리를 이동하는데 필요한 최소 거리 저장
        dp = new int[d+1];
        for (int i = 0; i <= d; i++) {
            dp[i] = i;
        }

        // 방법 1. DP
        getShortestPath();
    }

    static void getShortestPath() {
        for(int i=0; i<= d; i++) {
            if(i> 0) {
                // 지름길X, 고속도로 이동
                dp[i] = Math.min(dp[i], dp[i-1] + 1);
            }

            for(int [] path : graph) {
               int start = path[0];
               int end = path[1];
               int dist = path[2];

               if(i==start && end <= d) {
                   dp[end] = Math.min(dp[end], dp[start] + dist);
               }
            }
        }

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

풀이 과정(풀이 시간 : 40분)

최소 경로를 구해야 하므로, DP 풀이를 떠올리게 되었다.

 

1. dp[i]는 거리 i까지 이동하는데 걸리는 최소 시간을 저장한다. 초기에는 각 거리만큼 해당하는 시간을 저장해 놓는다.

2. 각 거리마다 지름길이 있는 길을 확인해서, 같은 시작점이면서 도착점이 d보다 작거나 같다면, dp 배열을 갱신한다.
3. 도착 지점(d)에 해당하는 dp 배열의 값을 반환한다.

내일은 면접에 대비하여 Kotlin 앱 개발 관련 개념을 복기해보고자 한다.

99클럽, Til, 개발자취업, 오블완, 코딩테스트준비, 티스토리챌린지, 항해99