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

링크: 1446번: 지름길 (acmicpc.net)

1446번: 지름길

문제

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

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

입력

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

출력

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

---

풀이

DP로 쉽게 풀 수 있다.

주어진 길이까지 이동하는데 걸리는 최소 시간을 DP테이블에 저장해나가면 된다.

먼저 기본적으로 도착 위치가 n이라면 걸리는 시간은 n일 것이고

모든 지름길을 조사해보면서 시간이 더 적게 걸리는 경우가 있다면 이를 반영해주면 된다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001];
int highway[13][3]; // 시작위치, 도착위치, 길이

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

    int n, d;
    cin >> n >> d;

    // 지름길 입력 받음
    for (int i = 1; i <= n; i++){
        cin >> highway[i][0] >> highway[i][1] >> highway[i][2];
    }

    // base case 설정
    for (int i = 0; i <= d; i++){
        dp[i] = i;
    }

    // i까지 이동하는 데 걸리는 최소 시간을 조사
    for (int i = 1; i <= d; i++){
        // n개의 지름길을 모두 조사
        for (int j = 1; j <= n; j++){
            if (highway[j][1] == i){ // 지름길의 도착지점이 i라면
                if (dp[i] > dp[highway[j][0]]+highway[j][2]){
                    dp[i] = dp[highway[j][0]]+highway[j][2];
                    // i+1번째 이후의 최소시간을 모두 반영해주는것에 주의
                    for (int k = i+1; k <= d; k++){
                        dp[k] = dp[i]+(k-i);
                    }
                }
            }
        }
    }

    cout << dp[d];
}