[BOJ/C++] 1446 지름길 : DP

문제

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

풀이

DP

• v[i] : 길 i로 가는 최소 비용

  • v[i]로 가는 지름길 ⭕ : v[i-1] + 1
  • v[i]로 가는 지름길 ❌ : min(v[i-1] + 1, 출발지의 비용 + 지름길의 거리)

• 0부터 D까지 가며 최댓값 갱신

지름길 정보 이런 식으로 배열에 저장
route[0]
route[1]
route[2]
⁞
route[50] = {0, 10}, {0, 20}
⁞
route[100] = {50, 10};

코드

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

using namespace std;

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

	int N, D;
	cin >> N >> D;
	vector<int> v(D + 1, 999999999);
	vector<pair<int, int>> route[10001];
	for (int i = 0; i < N; i++) {
		int start, end, len;
		cin >> start >> end >> len;
		route[end].push_back({ start, len });
	}
	
	v[0] = 0;
	for (int i = 1; i <= D; i++) {
		v[i] = v[i - 1] + 1;
		for (int j = 0; j < route[i].size(); j++) {
			v[i] = min(v[i], v[route[i][j].first] + route[i][j].second);
		}
	}

	cout << v[D];

	return 0;
}