[BOJ/Silver 1] 백준 1446 지름길(C++)

문제 링크

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

 

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

 

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

 

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

 

예제 입력 1

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

예제 출력 1

70

예제 입력 2

2 100
10 60 40
50 90 20

예제 출력 2

80

예제 입력 3

8 900
0 10 9
20 60 45
80 190 100
50 70 15
160 180 14
140 160 14
420 901 5
450 900 0

예제 출력 3

432

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

먼저 지름길의 정보를 정리한다.

지름길의 시작점 0부터, 지름길의 정보를 바탕으로 0부터 D까지 운전해야 하는 거리의 최솟값을 각각 기록해둔다.

어떤 도착점 To가 있다고 치고, 어떤 지름길의 시작점이 A, 도착점이 B, 거리가 C라고 할 때, To까지 도착하는 데 운전해야 하는 거리는 지금까지 기록해 두었던 To까지 운전하는 데 걸리는 거리(DP[To)와, A까지 오는 데 운전해야 하는 거리와 B에서 To까지 운전해야 하는 거리와 C를 합산한 결과(DP[A] + (To - B) + C) 둘 중 최솟값이 된다.

지름길은 최대 12개까지만 존재하기 때문에, 0부터 10,000까지 도달하기 위해 운전해야 하는 거리 각각을 기록하는 데 최악의 경우 120,000번의 연산만 하면 되기 때문에 그렇게 오랜 시간이 걸리지 않는다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 10001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, D, A, B, C;
int DP[MAX];
vector<pair<int, int> > Vec[MAX];

void init() {
	for (int i = 0; i < MAX; i++) {
		DP[i] = i;
	}
}

void input() {
	cin >> N >> D;
	for (int i = 0; i < N; i++) {
		cin >> A >> B >> C;
		Vec[A].push_back(make_pair(B, C));
	}
}

void settings() {
	for (int i = 0; i <= D; i++) {
		for (int j = 0; j < (int)Vec[i].size(); j++) {
			int To = Vec[i][j].first;
			int Cost = Vec[i][j].second;
			for (int k = To; k <= D; k++) {
				DP[k] = min(DP[k], DP[i] + Cost + (k - To));
			}
		}
	}
}

void find_Answer() {
	cout << DP[D] << "\n";
}

int main() {
	FASTIO
	init();
	input();
	settings();
	find_Answer();

	return 0;
}​