지름길 C++ - 백준 1446

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

이 문제는 dp, 다익스트라로 풀리는 문제이다.

처음에는 다익스트라 연습용으로 푼 문제였는데,

다시 생각해보니까 dp로도 풀 수 있는 문제였다.

비슷한 엣코더 문제 (최근 ABC340에 출제된 문제이다.)

(엣코더 문제는 다익스트라로 풀어야 한다. 전 스테이지로 가는 경우가 있기 때문에...)

이 문제는 앞으로 가는 경우만 있기 때문에 dp로 충분히 가능하다.

다익스트라를 사용한 코드이다.

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

vector<pair<int, int>> graph[10001];
int dp[10001];
int s,p,l;
int n,d;

void dijkstra(){
    priority_queue<pair<int, int>,vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0,0});
    dp[0]=0;
    while(!pq.empty()){
        int dist=pq.top().first;
        int now=pq.top().second;
        pq.pop();
        if(dp[now]<dist) continue;
        for(int i=0;i<graph[now].size();i++){
            int cost=dist+graph[now][i].second;
            if(cost<dp[graph[now][i].first]){
                dp[graph[now][i].first]=cost;
                pq.push({cost,graph[now][i].first});
            }
        }
    }
    cout << dp[d];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> d;
    fill(dp,dp+d+1,INF);
    for(int i=0;i<n;i++){cin >> s >> p >> l; graph[s].push_back({p,l});}
    for(int i=0;i<d;i++) graph[i].push_back({i+1,1});
    dijkstra();
}

아래는 dp를 사용한 코드이다.

#include <bits/stdc++.h>
using namespace std;

int n,d;
int dp[10001];
vector<pair<int, int>> v[10001];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> d;
    for(int i=0;i<n;i++){int s,e,l;cin >> s >> e >> l;v[e].push_back({s,l});}
    for(int i=1;i<=d;i++){
        dp[i]=dp[i-1]+1;
        for(int j=0;j<v[i].size();j++){
            dp[i]=min(dp[i],dp[v[i][j].first]+v[i][j].second);
        }
    }
    cout << dp[d];
}