https://www.acmicpc.net/problem/1006
# Approach)
타일링문제와 상당히 흡사하다. 고로 DP를 떠올려보자.
First Try(Failed)
# Definition)
$dp[i][j] :$ $min \ value \ when$ $inner \ circle \ is$ $filled \ to \ index \ i$, $and \ outer \ j$
$in[i] :$ $cost \ of \ index \ i $ $of \ inner \ circle$
$out[i] :$ $cost \ of \ index \ i$ $of \ outer \ circle$
소대가 한칸을 커버하는 경우와 두칸을 커버하는 경우가 있을 것이다.
- 한칸을 커버한다면
$ inner:$ $ dp[i+1][i] = min(dp[i+1][j], dp[i][j] + 1) $
$ outer:$ $ dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1) $
- 두칸을 커버한다면
$ inner: $ $ if \ in[i+1]+in[i+2] \leq w $ $ then $ $dp[i+2][j] = min(dp[i+2][j], dp[i][j] + 1) $
$ outer: $ $ if \ out[i+1]+out[i+2] \leq w $ $ then $ $ dp[i][j+2] = min(dp[i][j+2], dp[i][j] + 1) $
$ inner+outer: $ $ if \ in[i+1]+out[i+1] \leq w $ $ then $ $dp[i+1][j+1] =$ $min(dp[i+1][j+1], dp[i][j] + 1)$
이를 바탕으로 대략적인 점화식을 써보면
$ dp[i][j] =$ $ min( dp[i-1][j]+inner[i],$ $dp[i][j-1] + outer[j],$ $ dp[i-2][j] + inner[i-1],$ $ dp[i][j-2] + outer[j-1] ) $
정도로 표현될 것이다. (깔끔함을 위해 부수적인 조건들은 생략하였다)
1
2
3
4
5
6
7
8
9
10
11
int cdp(int ci, int cj) {
if(ci == si && cj == sj) return 0;
if(dp[ci][cj] != INF) return dp[ci][cj];
int& ref = dp[ci][cj];
if(ci > si+1 && inner[ci]+inner[ci-1] <= w) ref = min(ref, cdp(ci-2, cj)+1);
else if(ci > si) ref = min(ref, cdp(ci-1, cj)+1);
if(cj > sj+1 && outer[cj]+outer[cj-1] <= w) ref = min(ref, cdp(ci, cj-2)+1);
else if(cj > sj) ref = min(ref, cdp(ci, cj-1)+1);
if(ci == cj && ci > si && cj > sj && inner[ci] + outer[cj] <= w) ref = min(ref, cdp(ci-1,cj-1) + 1);
return dp[ci][cj];
}
대략 이런 느낌으로 재귀 함수를 이용하여 메모제이션 배열을 채웠고 TLE를 받았다.
$dp[i][j] :$ $min \ value \ when$ $inner \ circle \ is$ $filled \ to \ index \ i,$ $and \ outer \ j$
의 정의로부터 배열의 크기는 $10001\times10001$ 이다.
배열의 모든 $i, j$에 대해서 dp[i][j]를 계산해주고 있으니
$O(n^2)>O(10^8)$ 로 당연히 시간 초과가 날 수 밖에 없었다.
해결하기 위해서는 $O(n^2)$ 보다 낮은 상한의 과정으로 처리를 해주어야 할 것이다.
Improvement
접근을 바꿔서 효율적으로 개선해보자.
기술하기 편하도록 소대가 커버하는 구역을 타일로 덮는다고 생각하여 타일링문제로 치환하겠다.
모든 타일이 덮힌 최적의 해에서 반대로 타일을 하나 씩 빼가보자.
타일을 덮어간 과정을 역으로, 즉 타일을 역순으로 하나씩 제거할때마다 ‘이전 상태‘로 돌린다고 표현하겠다.
- 초기상태: dp[n][n]으로 inner와 outer의 모든 칸이 타일로 덮혀있고 최소의 타일을 사용하여 덮은 최적해를 생각하자. 이때, 이전 상태로 돌리면 inner 혹은 outer에서 길이 1 또는 2의 타일을 하나 제거 할 것이다.
1-A) 길이가 1인 타일을 제거한 경우:
타일로 덮혀진 inner와 outer의 길이차는 1이다.
1-B) 길이가 2인 타일을 제거한 경우:
일반성을 잃지 않고 길이가 2인 타일을 outer에서 제거했다고 가정하자.
inner에서도 마지막 타일을 제거해보자.
여기서도 두가지의 경우가 있을 있다.
1-B-a) 길이가 1인 타일인경우: 이전상태의 타일로 덮혀진 inner, outer의 길이차는 1이다.
1-B-b) 길이가 2인 타일인경우: 이전상태의 타일로 덮혀진 inner, outer의 길이차는 0이다.
이쯤에서 최적해의 타일을 덮어간 과정의 모든 중간과정은, 타일로 덮혀진 inner, outer의 길이차가 0 또는 1인 상태로만 구성할 수 있다는 것을 눈채챌 수 있을 것이다.
- 귀납적 연결:
이전상태의 타일로 덮혀진 inner, outer의 길이차가 0 또는 1인 상태의 이전 상태도
모두 타일의 길이의 차가 0 또는 1인 상태로 표현 할 수 있다.
2-A) 타일로 덮혀진 inner, outer의 길이차가 0인 경우:
1-A, 1-B에서 기술한 단계를 거치면 표현이 가능하다는 것을 알 수 있다.
2-B) 타일로 덮혀진 inner, outer의 길이차가 1인 경우:
길이가 긴쪽에서 타일을 하나 제거하자.
2-B-a) 제거한 타일의 길이가 1인경우:
이전상태의 타일로 덮혀진 inner, outer의 길이차는 0이다.
2-B-b) 제거한 타일의 길이가 2인경우:
타일로 덮혀진 inner, outer의 길이차는 1이다.
따라서 1과 2에 의해서 귀납적으로 최적해의 모든 과정은 타일로 덮혀진 inner, outer의 길이차가 0 또는 1인 상태로 표현 할 수 있다는 것을 알 수 있다.
시간복잡도도 LTE를 받던
$\{$ $\left(i, j\right) | i,j \in \mathbb{N} \land$ $1 \leq \forall i,j \leq n$ $\}$ $ \implies O(n^2)$
에서
$\{$ $\left(i, j\right) | i,j \in \mathbb{N} \land$ $1 \leq \forall i,j \leq n \land (|i-j|=1\lor i=j)$ $\}$ $ \implies O(n)$
으로 개선되게 되고 TLE를 면할 수 있을 것이다.
이제 원형으로 이어진 부분의 처리만 생각해주면 된다.
이는 $outer[1], outer[n]$이 겹칠 수 있고, $inner[1], inner[n]$이 겹칠 수 있으니 총 4가지의 상태이고 이는 단순 분기로 충분히 처리 가능하다.
디버깅에 시간이 꽤 걸렸는데 DP는 정의를 최대한 깔끔하게 하고 인덱스 실수에 주의해야 이와 같은 마음 아픈 경험을 하지 않을 수 있을 것이다.
Definition)
$dp[idx][state]$ $ ( 1 \leq idx \leq n, 0 \leq state < 3) $
길이의 차가 0또는 1이니 state는 3가지의 상태를 가질 것이다
state 0: 길이가 같은 경우
state 1: outer의 길이가 inner의 길이보다 긴 경우
state 2: inner의 길이가 outer의 길이보다 긴 경우
cdp함수를 호출하기전에 dp를 채우기시작하는 인덱스 si에 앞서 dp[si][]의 값들을 채워준다.
cdp함수의 if문에서 $ci-1 >= si$ 가 아닌 $ci-1 \geq si -1$임을 유의하자.
($outer[1], outer[n]$ 혹은 $inner[1], inner[n]$이 겹친경우 dp[2]까지를 초기화하고
cdp에서 탐색은 3부터 하는것으로 넘겨주었다.
따라서 $ci-1\geq 3$으로 작성하는 실수를 하기 쉽지만
$inner[2]$ 혹은 $outer[2]$에서 relax되는 경우도 고려해주어야하니
$ci-1 \geq 2$여야 할 것이다).
#Code(c++)
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
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define pf first
#define ps second
#define pii pair<int,int>
#define ll long long
#define lll __int128
#define endl "\n"
#define nulls '\0'
#define dkdk " "
#define print(a, i) cout << "debug: " << a << dkdk << " ckp: " << i << endl;
const int INF = 987654321;
const ll INFLL = 1e13;
const int mod = (int)1e9+7;
const int N = 802;
const int st = 50;
int n, m, t, w;
int dp[10001][3];
int inner[10001];
int outer[10001];
int cdp(int si, int ei) {
for(int ci = si; ci <= ei; ci++) {
dp[ci][1] = dp[ci][2] = dp[ci-1][0] + 1;
if(ci >= si && outer[ci] + outer[ci-1] <= w) dp[ci][1] = min(dp[ci][1], dp[ci-1][2] + 1);
if(ci >= si && inner[ci] + inner[ci-1] <= w) dp[ci][2] = min(dp[ci][2], dp[ci-1][1] + 1);
dp[ci][0] = 1 + min(dp[ci][1], dp[ci][2]);
if(inner[ci] + outer[ci] <= w) dp[ci][0] = min(dp[ci][0], dp[ci-1][0] + 1);
if(ci-1 >= si-1 && outer[ci] + outer[ci-1] <= w && inner[ci] + inner[ci-1] <= w) dp[ci][0] = min(dp[ci][0], dp[ci-2][0] + 2);
}
return dp[ei][0];
}
void solve() {
for0(i, n+1) for0(j, 3) dp[i][j] = INF;
dp[0][0] = dp[0][1] = dp[0][2] = 0;
int ans = cdp(1, n);
bool bi = inner[1] + inner[n] <= w, bj = outer[1] + outer[n] <= w;
if(bi) {
for0(i, n+1) for0(j, 3) dp[i][j] = INF;
dp[2][2] = 2; dp[2][1] = 2 - (outer[1] + outer[2] <= w);
dp[2][0] = min({ dp[2][1]+1, dp[2][2]+1, 3 - (inner[2] + outer[2] <= w) });
cdp(3, n);
ans = min(ans, dp[n][1] + 1);
}
if(bj) {
for0(i, n+1) for0(j, 3) dp[i][j] = INF;
dp[2][1] = 2; dp[2][2] = 2 - (inner[1] + inner[2] <= w);
dp[2][0] = min({ dp[2][1]+1, dp[2][2]+1, 3 - (inner[2] + outer[2] <= w) });
cdp(3, n);
ans = min(ans, dp[n][2] + 1);
}
if(bi && bj) {
for0(i, n+1) for0(j, 3) dp[i][j] = INF;
dp[1][0] = dp[1][1] = dp[1][2] = 0;
cdp(2, n-1);
ans = min(ans, dp[n-1][0]+2);
}
cout << ans << endl;
}
int main() {
FASTIO;
cin >> t;
while(t--) {
cin >> n >> w;
for1(i, n+1) cin >> inner[i];
for1(i, n+1) cin >> outer[i];
solve();
}
}