[C++]백준(BOJ) 1446 - 지름길(DP)

 

난이도 : 실I

풀이 시간 : 40분

알고리즘 유형 : DP, 다익스트라

풀이 방법 : d만큼 순회 해서 최솟값 저장(DP)

 

 

문제 예시 🚗💨

이 문제는 매일 아침 고속도로를 지나 학교에 가는 세준이가,
고속도로에 존재하는 지름길을 이용해 최단 거리로 목적지에 도달하는 방법을 찾는 문제입니다.

 

문제를 해결한 방식: 동적 계획법 (DP) 💡

이 문제에서는 동적 계획법을 사용하여 각 위치까지의 최단 거리를 계산합니다.

DP 방식으로 문제를 푼 이유:

• 동적 계획법을 사용하면, 각 위치까지의 최단 거리를 구할 때 이전 값들만 사용하여
  효율적으로 갱신할 수 있습니다. 고속도로를 따라 1km씩 주행하면서 거리를 갱신하고,
  지름길을 고려할 때도 그 값을 갱신하는 방식이 DP의 핵심입니다.

시간제한은 2초이며, N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수입니다.

시간 복잡도는 정렬에 O(NlogN) + O(d) 입니다.

N은 12가 초과될 수 없으며 d는 10,000이 초과될 수 없기 때문에 시간은 넉넉해보입니다.

 

 

아래는 코드입니다.

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

using namespace std;

int n, d, a, b, c;
vector<int> dist;


vector<tuple<int, int, int>> route;

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

	cin >> n >> d;

	dist.resize(d + 1);
	fill(dist.begin(), dist.end(), 2e9);

	for (int i = 0; i < n; ++i)
	{
		cin >> a >> b >> c;
		route.push_back({b, a, c});
	}

	sort(route.begin(), route.end());

	int route_len = route.size();
	int index = 0;

	dist[0] = 0;

	for (int i = 1; i <= d; ++i)
	{
		while (index < route_len)
		{
			auto [des, src, cost] = route[index];

			if(i != des)
				break;

			if (i == des)
			{
				++index;
				dist[i] = min(dist[i], dist[src] + cost);
			}
		}

		dist[i] = min(dist[i], dist[i - 1] + 1);
	}

	cout << dist[d];

	return 0;
}