코드 복사/붙여넣기 하는 당신이 아름답습니다.

2618 : 경찰차

풀이

dp[i][j] = 경찰차1이 i번째 사건, 경찰차2가 j번째 사건의 위치에 있을 때 거리 합의 최소값
일반성을 잃지 않고, max(i, j)까지의 사건들을 모두 처리했다고 하자.
지금 처리할 사건을 k번째라고 하자. (k = max(i,j)+1)
dst(i, j)는 i번째 사건과 j번째 사건 사이의 거리를 구하는 함수라고 하자.

경찰차1이 k번째 사건을 처리하려면, dp[k][j] = dp[k-1][j] + dst(k, k-1)
경찰차2가 k번째 사건을 처리하려면, dp[i][k] = dp[i][k-1] + dst(k, k-1)

점화식을 잘 정의했다면 여기까지 어렵지 않게 떠올릴 수 있다.

하지만 k-1 = j이거나 i = k-1인 경우는 따로 처리해 주어야 한다.
왜냐면 문제에서 어떤 사건을 두 경찰차가 동시에 처리하는 경우는 없기 때문이다.

이 경우는 0 ~ k-2까지의 모든 값을 다 고려해 주면 된다:
dp[k][j] = dp[{0 ~ k-2}][j] + dst(k, {0 ~ k-2})
dp[i][k] = dp[i][{0 ~ k-2}] + dst(k, {0 ~ k-2})

나중에 값을 tracing 하는 코드가 좀 귀찮은데 이건 알아서 잘 짜 주면 된다.

이게 중등부 2번 문제라니 놀라울 따름이다 (…)

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int n_ = 1001;

int n, w, x[n_+2], y[n_+2], dp[n_][n_], t1[n_][n_], t2[n_][n_];

inline int dst(int a, int b, int t) {
    if (!a) {
        a = t ? 1002 : 1001;
    }
    return abs(x[b]-x[a]) + abs(y[b]-y[a]);
}

inline void calc(int a, int b, int c, int d, int e, int f, int g) {
    if (dp[a][b] > dp[c][d]+dst(e,f,g)) {
        dp[a][b] = dp[c][d]+dst(e,f,g);
        t1[a][b] = g;
        t2[a][b] = g ? d : c;
    }
}

void trace(int i, int j) {
    if (!i && !j) {
        return;
    }
    if (!t1[i][j]) {
        trace(t2[i][j], j);
    }
    else {
        trace(i, t2[i][j]);
    }
    printf("%d\n", t1[i][j]+1);
}

void input() {
    scanf("%d %d", &n, &w);
    for (int i = 1; i <= w; i++) {
        scanf("%d %d", &x[i], &y[i]);
    }
    memset(dp, 0x3f, sizeof(dp));
    x[1001] = y[1001] = 1; dp[1][0] = dst(0,1,0);
    x[1002] = y[1002] = n; dp[0][1] = dst(0,1,1);
    t1[1][0] = 0; t1[0][1] = 1;
}

void process() {
    for (int i = 0; i <= w; i++) {
        for (int j = 0; j <= w; j++) {
            if (i == j) {
                continue;
            }
            else if (i && i == j-1) {
                for (int k = 0; k <= j-2; k++) {
                    calc(i,j,i,k,k,j,1);
                }
            }
            else if (j && j == i-1) {
                for (int k = 0; k <= i-2; k++) {
                    calc(i,j,k,j,k,i,0);
                }
            }
            else if (i < j) {
                calc(i,j,i,j-1,j-1,j,1);
            }
            else {
                calc(i,j,i-1,j,i-1,i,0);
            }
        }
    }
}

void output() {
    int ans = 2e9, flag, pos;
    for (int i = 0; i < w; i++) {
        if (ans > dp[i][w]) {
            ans = dp[i][w];
            pos = i;
            flag = 1;
        }
        if (ans > dp[w][i]) {
            ans = dp[w][i];
            pos = i;
            flag = 0;
        }
    }

    printf("%d\n", ans);
    if (flag) {
        trace(pos, w);
    }
    else {
        trace(w, pos);
    }
}

int main() {
    input();
    process();
    output();

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2019-01-22 02:06

Read more posts by this author