풀이
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이