[ 백준 / C++ ] 1446 : 지름길

[ 문제 ]

 

1446번: 지름길

 

[ 접근방법 ]

 

DP를 활용하여 O(N + D) 만에 문제를 해결할 수 있다.

 

dp[ i ] = i 킬로미터까지의 최솟값.

 

지름길에 따라 dp 테이블을 최신화 해주면서 진행했다.

 

만약 역주행이 가능하다면, 다익스트라 알고리즘을 활용할 것 같다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, d, dp[10010];
vector<pair<int, int>> vec[10010];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> d;

    for(int i = 0; i < n; i++){
        int p, q, r;
        cin >> p >> q >> r;
        vec[q].push_back({p, r});
    }

    for(int i = 1; i <= d; i++){
        dp[i] = dp[i - 1] + 1;
        for(auto [j, cost] : vec[i]){
            dp[i] = min(dp[i], dp[j] + cost);
        }
    }

    cout << dp[d];

    return 0;
}