[백준] 10653번 마라톤 2 (C++)

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

 

 

 

이 문제는 N개의 체크포인트가 존재하고 각 체크포인트마다 x, y좌표가 주어지며 K만큼 건너뛸 수 있는 횟수가 주어질때
도착 지점까지 K만큼 건너뛰었을때 최소 거리를 출력하는 문제이다.

 

문제를 보고 최단거리라고 생각을 해서 다익스트라 알고리즘을 사용하면 되지 않을까 싶었다.

하지만 구현을 하다 보니 건너뛴 횟수를 카운트를 해준다 한들 내가 이전에 어느 지점에서 건너 뛰었는지에 대한 정보들을 다 기록해 줘야 하기 때문에

 

다익스트라 알고리즘으로 구현하기는 힘들다고 판단하였다.

 

이후 어차피 N개의 체크포인트를 순서대로 방문해야 하기 때문에 순서성이 존재하여 dfs, dp를 사용하여 풀 수 있다고 생각했다.

 

이후에 dp를 점화식을 사용하는 부분에서 굉장히 오랜 시간이 걸렸다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, K;
vector<pii> v;

int dist(int a, int b, vector<pii> &vec) {
    return abs(vec[a].first - vec[b].first) + abs(vec[a].second - vec[b].second);
}

void solve() {
    vector<vector<int>> dp(N, vector<int>(K+1, MAX));
    dp[0][0] = 0;

    for(int i = 1; i < N; i++) {
        for(int j = 0; j < i && j <= K; j++) {
            for(int k = 0; k <= j; k++) {
                dp[i][j] = min(dp[i][j], dp[i-k-1][j-k] + dist(i-k-1, i, v));
            }
        }
    }

    int answer = MAX;
    for(int i = 0; i <= K; i++) {
        answer = min(answer, dp[N-1][i]);
    }

    cout << answer;
}

void input() {
    cin >> N >> K;

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
}

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

    input();
    solve();
}

 

 

풀이과정을 하나씩 살펴보면

	vector<vector<int>> dp(N, vector<int>(K+1, MAX));
    dp[0][0] = 0;

    for(int i = 1; i < N; i++) {
        for(int j = 0; j < i && j <= K; j++) {
            for(int k = 0; k <= j; k++) {
                dp[i][j] = min(dp[i][j], dp[i-k-1][j-k] + dist(i-k-1, i, v));
            }
        }
    }

    int answer = MAX;
    for(int i = 0; i <= K; i++) {
        answer = min(answer, dp[N-1][i]);
    }

dp 배열을 미리 할당해 놓고 INF값으로 초기화 하였으며 시작점에서부터 최소값을 갱신할거기 때문에 시작점은 0으로 놓았다.

 

이후 점화식을 설명하면 i는 체크포인트를 나타내며 j는 건너뛴 횟수이며 k는 그 건너뛴 횟수중 이전에 건너뛴 개수를 나타낸다.

따라서 j는 체크포인트보다 작아야하며 K보다는 작거나 같아야 한다.

 

int dist(int a, int b, vector<pii> &vec) {
    return abs(vec[a].first - vec[b].first) + abs(vec[a].second - vec[b].second);
}

 

dist 함수를 살펴보면 a, b가 나타내는 것은 건너뛰었을때 도착한 지점에서 i(즉 현재 바라보는 체크포인트 좌표) 까지의 맨하탄 거리를 나타낸다.

시간복잡도는 O(N^3) 보다는 훨씬 작다고 생각하였으며 j가 안되는 경우가 많기 때문에 저거보다는 훨씬 작다고 생각한다.

 

 

회고록

점화식 세우는게 굉장히 까다로웠던 문제이다. 처음엔 2중 for문으로 풀릴 수 있지 않을까 생각했는데 다익스트라 구현때처럼

이전에 건너뛰었던 위치를 기록했어야 하기 때문에 3중 for문으로 구현하였다.