[백준 1446] 지름길

작성일 | In |

문제 링크

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

풀이

학교에서 더 멀어지는 쪽으로는 가지 않으므로 $0$부터 $D$까지 순서대로 dp 배열을 채울 수 있습니다. 시작하는 곳인 길이 $0$에서는 거리 $0$만큼 이동한 것으로 시작하고 나머지 길이 $[1,D]$는 모두 $INF$로 초기화 합니다. $i$에서 $i+1$로 $1$의 거리로 갈 수 있고 $i$에서 시작하는 지름길을 이용해 도착위치로 지름길의 기리만큼의 거리로 갈 수 있기에 각각 $min$으로 갱신한다면 $dp_D$에 들어있는 값이 문제의 정답입니다. 다익스트라를 이용한다면 $O(D \log D)$에 풀 수 있겠지만 이 풀이를 이용한다면 $O(N + D)$로 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, d, dist[10010];
vector<pair<int, int>> v[10010];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> d;

    for(int i=1;i<=d;i++) dp[i] = 1e9;
    for(int i=1;i<=n;i++){
        int a, b, c; cin >> a >> b >> c;
        v[a].push_back({b, c});
    }

    for(int i=0;i<d;i++){
        dp[i+1] = min(dp[i+1], dp[i] + 1);
        for(auto [x, y] : v[i]) dp[x] = min(dp[x], dp[i] + y);
    }

    cout << dp[d];
}