백준 BOJ 1446 - 지름길

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

1446번: 지름길

깔끔하게 풀어서 맘에드는문제

 

그래프 or 다익스트라로 푼 사람들이 몇몇 보이던데,

개인적으로는 DP로 푸는게 더 깔끔하지 않나 싶다.

 

$dp_i$ - 현재 위치가 i 일때 운전한 거리의 최솟값

다음 dp테이블의 정의에 따라 정답은 $dp_D$ 가 된다.

 

$dp_k$ 는 처음에 임의의 MAX값( 난 998244353으로 정했다 )

로 초기화해놓은 뒤,

두가지 경우

1. 지름길이 없는 경우 $dp_{k+1} = min( dp_{k+1}, dp_k + 1 )$
2. $k$에서 $K$로의 지름길이 있는 경우 $dp_K = min( dp_K, dp_k + 1 )$ 

 

각각에 대해서 dp 테이블을 최소값으로 갱신해주면 된다.

지름길 주행 없이도 끝가지는 갈수 있기 때문에 MAX값이 출력으로 나올 걱정은

안해도 되는 문제였다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define MAX 998244353
using namespace std;

vector<pair<int,int>> path[12345];

int dp[12345];

int main(){
	for(int i=0; i<12345; i++) dp[i] = MAX;
	int N,D;
	int a,b,c;
	
	cin >> N >> D;
	for(int i=0; i<N; i++){
		cin >> a >> b >> c;
		path[a].push_back({b,c});
	}
	
	dp[0] = 0;
	for(int i=0; i<=D; i++){
		dp[i+1] = min(dp[i+1], dp[i]+1);
		
		for(auto k : path[i]){
			dp[k.x] = min(dp[k.x], dp[i]+k.y);
		}
	}
	
	cout << dp[D];
	return 0;
}