백준 1446번 [지름길](C++)-yes6686- 티스토리

백준 문제 풀이: 1446 [지름길]

---

문제 링크: https://www.acmicpc.net/problem/1446

문제 설명:

길이가 d인 고속도로와 n개의 지름길이 주어집니다. 지름길은 고속도로의 특정 구간을 대체하며, 이동 시간을 줄일 수 있습니다. 주어진 지름길들을 적절히 활용하여 출발점에서 도착점까지의 최소 이동 시간을 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int dp[10001];
vector<pair<int, pair<int, int>>> v;

bool compare(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    if (a.first == b.first) {
        return a.second.first > b.second.first;
    } else {
        return a.first > b.first;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, d;
    cin >> n >> d;
    int a, b, c;

    // 초기화
    for (int i = 0; i <= d; i++) {
        dp[i] = i;
    }

    // 지름길 정보 입력
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        v.push_back({a, {b, c}});
    }

    // 지름길을 정렬
    sort(v.begin(), v.end(), compare);

    // 지름길을 이용하여 최소 거리 계산
    while (!v.empty()) {
        a = v.back().first;
        b = v.back().second.first;
        c = v.back().second.second;
        v.pop_back();

        if (b > d) continue;       // 도착지가 고속도로의 끝보다 큰 경우 무시
        if (b - a <= c) continue;  // 지름길이 시간 절약이 되지 않는 경우 무시

        dp[b] = min(dp[b], dp[a] + c);
        for (int j = 1; j <= d; j++) {
            dp[j] = min(dp[j], dp[j - 1] + 1);
        }
    }

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

---

코드 설명

• 핵심 알고리즘: 다이나믹 프로그래밍과 정렬을 결합하여 지름길을 효율적으로 처리합니다.
• 구현 세부사항:
  • 지름길 정보를 시작점을 기준으로 정렬한 뒤, 뒤에서부터 차례로 처리합니다.
  • 각 지름길의 시작점과 도착점을 고려해 유효한 경우 최소 거리를 갱신합니다.
  • 모든 지름길을 처리한 뒤, dp 배열에 저장된 최소 이동 시간을 출력합니다.
• 시간 복잡도: O(n log n + d)
  • 지름길 정렬: O(n log n)
  • dp 배열 갱신: O(d)

---

결과

지름길을 활용하여 출발점에서 도착점까지의 최소 이동 시간을 계산합니다. 이 코드에서는 지름길이 유효하지 않은 경우도 정확히 처리하며, 시간과 메모리 효율성을 유지합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!