문제

백준 1446번 문제

코드

#include <bits/stdc++.h>

using namespace std;

int N, D;
int dp[10004];

struct Path
{
    int start;
    int end;
    int distance;
};

Path p[13];

bool Compare(Path& p1, Path& p2)
{
    return p1.start < p2.start;
}

int main()
{
    cin >> N >> D;

    for (int i = 1; i <= D; i++)
    {
        dp[i] = i;
    }

    for (int i = 0; i < N; i++)
    {
        Path path;
        cin >> path.start >> path.end >> path.distance;
        p[i] = path;
    }

    sort(p, p + N, Compare);

    for (int i = 0; i < N; i++)
    {
        if (p[i].end > D) continue;

        int end = p[i].end;
        dp[end] = min(dp[end], dp[p[i].start] + p[i].distance);

        for (int j = end + 1; j <= D; j++)
        {
            dp[j] = min(dp[j], dp[j - 1] + 1);
        }
    }

    cout << dp[D];

    return 0;
}

풀이

DP 문제이다

우선 지름길을 자료구조에 저장하기 위해 Struct 구조체를 선언하고 배열을 선언함

그리고 DP[i]는 실제 거리 i만큼 갔을 때 세준이가 운전해야 하는 최소 달린 거리이다

그래서 처음에 DP[i] = i로 초기화 해준다(실제 거리 = 달린 거리)

그 다음 지름길 배열을 순회하면서 DP를 시작

먼저 지름길은 일방통행이므로 지름길의 끝이 D를 넘어가면 고려 대상이 아니다

i번째 지름길의 끝을 end라고 하면 dp[end]는 기존의 dp[end] 값과 지름길의 출발인 dp[start]와 지름길의 길이를 더한 값 중 최솟값이다

dp[end]를 구했으면 end 이후의 dp 배열을 초기화해줘야 한다. end + 1부터 D까지 1씩 증가한 값으로 초기화하는데 기존 값보다 크다면 초기화 안함

처음에는 문제 풀 때 지름길 배열을 정렬을 안해줬다가 틀렸어서 지름길의 출발점을 기준으로 오름차순 정렬 후 제출하니까 해결했다