문제 출처

1. 문제설명

  • 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다.
  • 고속도로에는 지름길이 있다.
  • 세준이가 운전해야 하는 거리의 최솟값을 구하라.



2. 알고리즘 설계

  • 가중치가 0 또는 1이 아니라, 여러개 이므로, BFS는 사용할 수 없다.
  • 알고리즘 분류는 다익스트라, DP이지만,
  • DP 방식으로 해결했다.
    • 1부터 목적지까지 하나씩 증가시킨다.
    • 증가시키다가, 해당 지점의 지름길이 있다면,
      • 지름길로 가는 것과 그냥 가는 것 중 빠른 걸로 갱신한다.



3. 로직

  • DP의 핵심은 점화식이므로, 점화식으로 설명하겠다.
  • 아래의 코드는 지름길이 있는 지점을 방문했을 때이다.
    • 지름길 없이 그냥 왔을 때의 값
    • 지름길의 시작 지점 부터 가중치를 더했을 때의 값
    • 비교
      • DP[i] = min(DP[i], min(DP[i - 1] + 1, DP[root.src] + root.weight))



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 0x3f3f3f;
const int SZ = 10001;

int n, d;
vector<int> DP(SZ, INF);
vector<pii> v[SZ];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> d;

	for (int i = 0; i < n; i++) {
		int src, dest, w;
		cin >> src >> dest >> w;
		v[dest].push_back({ src, w });
	}

	DP[0] = 0;
	for (int i = 1; i <= d; i++) {
		if (v[i].size() == 0) DP[i] = DP[i - 1] + 1;
		else {
			for (auto a : v[i])
				DP[i] = min(DP[i], min(DP[i - 1] + 1, DP[a.first] + a.second));
		}
	}

	cout << DP[d];
	return 0;
}