백준 2618번 : 경찰차
https://www.acmicpc.net/problem/2618
2618번: 경찰차
첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 ��
www.acmicpc.net
문제를 잘 읽어보면 모든 사건들을 각 사건마다 1번, 2번 경찰차중에 어느 경찰차가 해당 사건을 처리해야
최적해가 나올 지 구하는 DP문제임을 알 수 있다.
일단 가장 직관적인 해답은 두 경찰차의 좌표를 매개변수로 받는 부분 문제를 만드는 것이다.
DP[ind][x1][y1][x2][y2] : 지금 해결해야 하는 사건이 ind이고 경찰차1의 위치가 (x1, y1), 경찰차2의 위치가 (x2, y2)일 때 남은 사건을 해결하기 위한 최소 거리
이런 식으로 생각했을 때 직면하는 문제는 바로 메모이제이션의 범위가 너무 크다는것이다. 부분문제의 갯수만 세어 봐도 시간 초과와 메모리 초과가 모두 발생할 것이 뻔했다.
여기서 생각해 볼만한 것은 경찰차의 현재 좌표는 어떤 요소에 의해 특정될 수 있다는 것이다.
경찰차1의 좌표는 항상 둘 중 하나다.
case1. 경찰자 1이 아무 사건도 해결하지 않은 경우 : (1, 1)
case2. 경찰자 1이 최근에 해결한 사건의 좌표
경찰차2의 좌표 또한 비슷하다.
case1. 경찰자 2가 아무 사건도 해결하지 않은 경우 : (N, N)
case2. 경찰자 2가 최근에 해결한 사건의 좌표
그렇다면 매개변수로 전달되는 값을 굳이 해당 경찰차의 x, y값이 아닌 해당 경찰차가 최근의 해결한 사건번호로 한다면 어떨까?
DP[ind1][ind2][ind3] : 지금 해결해야 하는 사건이 ind1이고 경찰차1이 최근에 ind2번 사건을, 경찰차2가 최근에 ind1번 사건을 해결했을 때 남은 사건을 해결하기 위한 최소 거리
case1의 경우 사건 번호를 1번부터 시작하고 ind2나 ind3이 0일때를 따로 처리하면 된다.
그러나 아직도 문제가 있는데, 이렇게 최적화를 하여도 메모리가 부족하다는 것이다.
ind1, ind2, ind3의 범위는 모두 1에서 1000이다. 1000^3개의 int형 메모리를 할당한다면 4GB나 할당되기 때문에
문제에서 주어진 메모리 제한 128MB를 훌쩍 넘겨 버린다.
바로 전에 해결했던 사건이 항상 최근의 사건이라는 사실을 이용해 보자.
저번 사건을 해결한 경찰차가 경찰차1인지 경찰차2인지만 알고 있다면 해당 경찰차의 좌표는 특정된다.
이를 이용하면 이런 식으로 최적화가 가능하다.
DP[ind1][ind2][who] : 현제 해결해야 하는 사건이 ind1이고 저번 사건을 who번 경찰차가 해결했으며 who번이 아닌 경찰차는 최근에 ind2번 사건을 해결했을 때 남은 사건을 해결하기 위한 최소 거리
who의 범위는 0, 1, 2이다. who가 0일 경우 이전에 해결된 사건이 존재하지 않는다는 뜻이고, 1,2는 각각 저번 사건을 경찰차1, 경찰차2가 해결했다는 의미이다.
이제 할당해야 하는 메모리는 12MB로 크게 줄어들었다. 이 정도면 문제를 여유롭게 해결할 수 있게 되었다.
또한, 이 문제는 최소 거리 뿐만 아니라 최소 거리를 만들기 위해 각 사건을 어떤 경찰차가 해결했는지 또한 출력하기를 요구한다. 따라서 부분 문제 별로 최적해를 위해 고른 선택을 choices라는 공간에 따로 저장해놓고 나중에 역추적하여 출력하는 기법을 이용했다.
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define F first
#define S second
using namespace std;
int N, W;
int DP[1001][1002][3];
//DP[a][b][c] : 현제 해결해야 하는 사건이 a이고 저번 사건을 c번 경찰차가 해결했으며 c번이 아닌 경찰차는 최근에 사건b를 해결했을 때 남은 사건을 해결하기 위한 최소 거리 int choices[1001][1002][3];//각 부분 문제에서 최적해를 위한 선택을 저장해놓는다
vector<pair<int, int>> vec;
int solve(int ind1, int ind2, int who) {
if (ind1 == W + 1) return 0;
if (DP[ind1][ind2][who] != -1) return DP[ind1][ind2][who];
pair<int, int> loc[2] = { {1,1}, {N,N} };
int ind3_1 = 0;//1번 경찰차가 최근에 해결한 사건번호
int ind3_2 = 0;//2번 경찰차가 최근에 해결한 사건번호
if (who != 0) {
loc[who - 1] = vec[ind1 - 1];//who번 경찰차가 저번 사건을 해결했기 때문에 who번 경찰차는 저번 사건의 발생지에 있다.
if(who == 1) ind3_1 = ind1 - 1;
else ind3_2 = ind1 - 1;
if (ind2 != 0) {
if (who == 1) {
ind3_2 = ind2;
loc[1] = vec[ind2];
}
else {
ind3_1 = ind2;
loc[0] = vec[ind2];
}
}
}
int one = abs(vec[ind1].F - loc[0].F) + abs(vec[ind1].S - loc[0].S) + solve(ind1 + 1, ind3_2, 1);
int two = abs(vec[ind1].F - loc[1].F) + abs(vec[ind1].S - loc[1].S) + solve(ind1 + 1, ind3_1, 2);
if (one <= two) {
choices[ind1][ind2][who] = 1;
return DP[ind1][ind2][who] = one;
}
else {
choices[ind1][ind2][who] = 2;
return DP[ind1][ind2][who] = two;
}
}
void printAnswer(int ind1, int ind2, int who){
if (ind1 == W + 1) return;
int choice = choices[ind1][ind2][who];
int ind3_1 = 0;
int ind3_2 = 0;
if (who != 0) {
if (who == 1) ind3_1 = ind1 - 1;
else ind3_2 = ind1 - 1;
if (ind2 != 0) {
if (who == 1) ind3_2 = ind2;
else ind3_1 = ind2;
}
}
cout << choice << "\n";
if (choice == 1) {
printAnswer(ind1 + 1, ind3_2, 1);
}
else {
printAnswer(ind1 + 1, ind3_1, 2);
}
}
int main() {
vec.push_back({ 0,0 });
memset(DP, -1, sizeof(DP));
cin >> N >> W;
for (int i = 0; i < W; i++) {
int x, y;
cin >> x >> y;
vec.push_back({ x,y });
}
cout << solve(1, 0, 0) << "\n";
printAnswer(1, 0, 0);
}
|
cs |
코드의 내용이다. 부분 문제가 3(W^2)개 존재하며 각 부분 문제를 해결하는데 O(1)의 시간이 걸리므로 시간 복잡도는 O(W^2)이며, 메모이제이션을 이용했기 떄문에 공간복잡도 또한 O(W^2)이다.
'알고리즘 문제풀이 공부' 카테고리의 다른 글
| 알고리즘 동아리 활동#2 이분 탐색 연습문제 풀이 (0) | 2020.11.27 |
|---|---|
| 알고리즘 동아리 활동#1 그리디 알고리즘 연습문제 풀이 (0) | 2020.11.27 |
| constructive algorithms에 대하여 #1 (0) | 2020.07.11 |
| [백준 17613] 점프 : 수의 규칙성을 이용한 최적화 (0) | 2020.04.28 |
| [백준 1398] 동전 문제 : 수의 규칙성을 이용한 최적화 (0) | 2020.04.27 |
