문제 요약 및 풀이
1
2
3
1. 두 경찰차가 모든 사건을 처리하러 이동해야 한다.
2. 모든 사건을 주어지는 순서대로 처리해야 한다.
3. 두 경찰차는 처음에 각각 (1, 1), (N, N)에 위치한다.
이때, 두 경찰차가 이동하는 최소 거리를 구해야 한다.
일단 먼저 모든 경우를 탐색한다고 생각해보고 접근해보자. 사건의 개수는 C개 (<= 1000)이다.
그럼 사건을 두 경찰차가 각각 배정받게 만들고, 이를 계산을 순서대로 해본다고 하자. 시간복잡도는 2^C 가 되며, 문제의 최대 범위로 입력이 들어올 경우 최대 2^1000 만큼 연산해야 한다.
무조건 시간초과가 뜰 것이다.
생각을 간단히 해보자.
만약에 첫번째 경찰차가 2번째 사건까지 처리하고, 두번째 경찰차가 4번째 사건까지 어찌저찌 처리했다 해보자.
그럼 다음으로 처리해야 하는 사건은 어떤 사건인가?
당연하게도 5번째 사건을 처리해야 한다.
왜? 바로 순서대로 사건을 처리해야 한다는 조건때문이다.
이 점을 이용해서 DP 식에 넣고 이용해보자.
1
2
3
4
5
i는 첫번째 경찰차의 마지막 위치라하고
j는 두번째 경찰차의 마지막 위치라 할 때
DP[i][j] = 두 경찰차가 이동한 최소 거리라 하자.
단, i와 j는 같을 수 없다. (i와 j가 같다는 것은 두 경찰차가 같은 사건을 처리했다는 의미이므로 배제해야 한다.)
DP[i][j] 를 이용해서 알아낼 수 있는 값은 어떤 것이 있을까?
첫번째 경찰차 또는 두번째 경찰차가 이동하는 경우일테니 아래와 같을 것이다.
1
2
3
4
5
6
7
8
// 첫번째 경찰차가 이동한 경우
int nxt = max(i, j) + 1;
DP[nxt][j]] = DP[i][j] + dis(points[i], points[nxt]);
// 두번쨰 경찰차가 이동한 경우
int nxt = max(i, j) + 1;
DP[i][nxt]] = DP[i][j] + dis(points[j], points[nxt]);
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
#define for1(s,n) for(int i = s; i < n; i++)
#define for1j(s,n) for(int j = s; j < n; j++)
#define foreach(k) for(auto i : k)
#define foreachj(k) for(auto j : k)
#define pb(a) push_back(a)
#define sz(a) a.size()
#define INF 100000000
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector <int> iv1;
typedef vector <vector<int> > iv2;
typedef vector <ll> llv1;
typedef unsigned int uint;
typedef vector <ull> ullv1;
typedef vector <vector <ull> > ullv2;
struct Point {
int y, x;
};
struct st {
Point p;
Point rev;
int cost;
};
struct cmp{
bool operator()(st a, st b){
return a.cost > b.cost;
}
};
int N;
int C;
Point points[1100];
int D[1100][1100];
Point back[1100][1100];
int dis(Point a, Point b) {
return abs(a.x - b.x) + abs(a.y - b.y);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> C;
for(int i = 0; i <= C + 1; i++)
for(int j = 0; j <= C + 1; j++) D[i][j] = INF;
points[0] = {1, 1};
points[1] = {N, N};
for(int i = 2; i <= C + 1; i++) cin >> points[i].y >> points[i].x;
priority_queue <st, vector<st>, cmp> q;
q.push({ {0, 1}, {0, 0}, 0});
while(!q.empty()) {
st here = q.top(); q.pop();
int y = here.p.y;
int x = here.p.x;
if(D[y][x] <= here.cost) continue;
D[y][x] = here.cost;
back[y][x] = here.rev;
int nxt = max(y, x) + 1;
if(nxt > C + 1) continue;
q.push({ {y, nxt}, here.p, here.cost + dis(points[x], points[nxt])});
q.push({ {nxt, x}, here.p, here.cost + dis(points[y], points[nxt])});
}
stack <Point> stk;
int ans = INF;
Point s;
for(int i = 0; i <= C + 1; i++) {
if(D[i][C + 1] < ans) {
ans = D[i][C + 1];
s = {i, C + 1};
}
if(D[C+ 1][i] < ans) {
ans = D[C + 1][i];
s = {C + 1, i};
}
}
cout << ans << "\n";
while(s.x != 0 || s.y != 0) {
stk.push(s);
s = back[s.y][s.x];
}
while(!stk.empty()) {
Point here = stk.top();
stk.pop();
if(stk.empty()) continue;
Point there = stk.top();
if(here.x != there.x) cout << 2;
else cout << 1;
cout << "\n";
}
}