https://www.acmicpc.net/problem/17424
17424번: 2xN 타일링과 쿼리
첫째줄에 N과 쿼리의 수를 나타내는 정수 Q가 공백으로 구분하여 주어진다. (1 ≤ N ≤ 105, 1 ≤ Q ≤ 2 x 105) 둘째줄부터 Q줄에 걸쳐 2가지 종류의 쿼리가 주어진다. 각 쿼리는 t x y꼴로 주
www.acmicpc.net
처음으로 푼 solved.ac 다이아 문제기 때문에 풀이를 써 보려고 한다.
개요
먼저 문제를 이해해야 하는데, 평범한 2xN 타일링과는 다르게 해당 위치에 있는 칸을 없애거나 다시 만드는 쿼리가 계속해서 주어지고, 쿼리마다 타일링 경우의 수를 출력해야 한다. 계속해서 쿼리를 받으며 업데이트 해주는 형태이기 때문에 세그먼트 트리가 생각난다. 하지만 세그먼트 트리의 합치기나 업데이트는 어떻게 구현해야 할까? 먼저 평범한 2xN 타일링의 경우를 생각해 보자.
f(n) = 2*n 의 격자를 2*1타일로 가득 채우는 경우의 수 라고 할 때, f(1) = 1, f(2) = 2이며, 세로로 하나 세우는 경우와, 가로로 두 개 세우는 경우로 나뉘어 3이상의 n에 대해 f(n) = f(n-1) + f(n-2)임을 쉽게 알 수 있다. 또한 이는 피보나치 수열의 점화식과 일치한다.
그렇다면 두 구간에 있는 격자를 합치려면 어떻게 해야 할까? 2*2 타일과 2*3 타일을 합치는 것을 생각해보자.
기본 아이디어 설계
case 1 : 구간의 경계에 걸치는 타일이 없는 경우이다. 이 케이스의 경우의 수는 그냥 2*2타일을 채우는 경우의 수와 2*3타일을 채우는 경우의 수의 곱, 즉 f(2) * f(3) = 2 * 3 = 6.
case 2 : 이번에는 경계를 걸치는 타일이 존재한다. 단순한 2*n 타일링의 경우 저렇게 두 개의 가로 블록이 경계를 걸치는 경우만이 존재한다. 따라서 이 케이스의 경우의 수는 왼쪽 구역에 남은 2*1타일과 오른쪽 구역에 남은 2*2 타일의 경우의 수를 곱한 것과 같음을 알 수 있다. 즉 f(1) * f(2) = 1 * 2 = 2.
두 케이스를 합쳐 보면 8개의 경우의 수가 존재함을 알 수 있다. 실제로 f(5)를 구해 보면 8이 나오는 것을 통해 검증 가능하다. 그렇다면 조금 일반화 해보자.
2이상의 a, b에 대해
f(a + b) = f(a) * f(b) + f(a - 1) * f(b - 1) 이다. 이를 통해 두 개의 범위를 합칠 수 있다.
아이디어 확장
이 문제는 위의 아이디어만으로 풀기에는 역부족이다. 도중에 칸을 없애는 쿼리 때문에 그냥 저렇게 합치는 걸로는 경우의 수를 제대로 셀 리가 없기 때문이다. 그러나 위의 아이디어에서 제일 중요한 것은 경계를 걸치는 타일의 케이스들만 생각하면 두 구간을 합칠 수 있다는 것이다. 본격적으로 세그먼트 트리를 설계해 보자.
왼쪽의 그림과 같이 설계하면 칸을 없애는 쿼리를 적용한 후에는 오른쪽의 모습이 될 것이다. 그렇다면 노드끼리 합치는 연산을 구현하려면 각 노드에는 어떤 정보를 담아야 할까? 양 끝 경계 4개의 상태에 따른 타일링 경우의 수를 모두 저장하여, 노드 하나당 2^4개의 정보를 담아 둔다면, 그 정보들을 이용하여 합칠 수 있을 것이다. 적어도 4개의 타일이 필요하므로 2*1이 아닌 2*2 타일을 리프 노드로 해야 한다.
양 끝 경계의 상태는 비트 마스킹으로 정보를 담아서 구현해 보자. s와 e는 쉬운 이해를 위해 이진수로 표현할 것이다.
arr[n][s][e] : n번 노드에서 왼쪽 끝 타일의 채워진 상태가 s, 오른쪽 끝 타일의 채워진 상태가 e일 때 남은 타일들을 채우는 경우의 수
이런 식으로 세그먼트 트리를 설계하면 대략 200000 * 4 * 4의 3차원 배열로 표현할 수 있을 것이다.
이제 트리를 초기화 해보자. 먼저 리프 노드(2*2타일)을 모두 채워 넣고, 부모 노드에서 자식 노드 2개를 합치는 작업을 하는 식으로 구현해야 한다. 즉, 2*2 타일의 경우의 수를 모두 생각해 봐야 하는데, 이는 약간의 수작업을 거쳐 주자.
s = 00, e = 00일 때 : 2
s = 11, e = 00일 때 : 1
s = 00, e = 11일 때 : 1
s = 10, e = 10일 때 : 1
s = 01, e = 01일 때 : 1
s = 11, e = 11일 때 : 1 (이미 다 채운 상태이므로 하나의 경우의 수가 있다고 친다.)
그 외 : 타일을 채울 수 없으므로 0
그리고 합치는 작업을 구현해야 하는데, 이는 아까의 기본 아이디어 설계를 확장해 보자.
이번엔 케이스가 4개다. 경계를 걸치는 타일이 하나만 존재하는 경우도 생각해야 하기 때문이다.
경계를 걸치는 타일을 이미 놓았다고 가정하고, 왼쪽, 오른쪽 구역의 각각 나머지 타일을 채우는 경우의 수를 생각하면 되는 것이다. 이를 식으로 표현해 보자. 리프가 아닌 노드의 번호 i와 00이상 11이하의 s와 e에 대해
위의 식이 성립한다. 모든 s, e에 대해 성립하므로 이 식으로 두 자식 노드를 합치는 것을 구현할 수 있다.
풀이 설계
이제 남은 것은 칸을 없애거나 다시 만드는 쿼리를 적용하는 것이다. 이는 비트 마스킹을 통해 리프 노드마다 현재 없어진 칸의 상태를 저장하는 배열을 따로 만들어 두고, 그 배열 속 값을 갱신한 뒤 그것에 따라 리프 노드를 직접 수정하면 된다. 예를 들어 리프 노드에서 왼쪽 위 칸을 없애는 쿼리를 적용했다고 치자.
여기서 s가 10 혹은 11이면 어떻게 될까? 해당 비트가 켜져있다는 것은 왼쪽 경계의 윗 칸이 채워졌다는 것을 뜻하는데, 칸을 없애버렸으므로 채운다는 것 자체가 성립하지 않는다, 즉 고려할 가치가 없으므로 0으로 초기화를 하면 된다.
그 외의 경우에는 없어진 칸의 상태와 s, e 상태의 합집합으로 생각하면 된다. 예를 들어 없어진 칸의 상태가 10, 00이고 s = 01, e = 00이면 합집합은 11, 00 이므로 s = 11, e = 00이라고 생각하고 1을 넣어 주는 식이다. 아까 전에 2*2타일에서의 경우의 수를 알아낸 적이 있으므로, 이를 그대로 전처리 해 두고 재활용하면 그나마 편하게 구현할 수 있다.
사실 이제껏 중요한 것을 하나 고려하지 않았다. N이 홀수인 경우에는 어떻게 해야 할까?
칸을 없애는 작업을 구현했다면 이것 또한 쉽게 해결할 수 있다. (N+1)/2 개의 리프노드를 만들고 마지막 리프노드에서 왼쪽 칸 2개를 없애 버리면 된다. N = 5인 경우를 그림으로 나타내면 다음과 같다.
이제 이 문제를 푸는 데 필요한 연산들을 구현하였으므로, 매 쿼리마다 트리의 루트의 s=0, e=0인 값을 출력하면 된다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll N, Q, nodeSz = 1, vec[200001][1 << 2][1 << 2];
ll base[1 << 2][1 << 2];
pair<int,int> now[50001];
void merge(int i) {
if (vec[i * 2 + 1][0][0] == -1)
for (int s = 0; s < 4; s++)
for (int e = 0; e < 4; e++)
vec[i][s][e] = vec[i * 2][s][e];
else {
for (int s = 0; s < 4; s++) {
for (int e = 0; e < 4; e++) {
ll val = 0;
for (int m = 0; m < 4; m++) {
val = (val + ((vec[i * 2][s][m] * vec[i * 2 + 1][m][e]) % MOD)) % MOD;
}
vec[i][s][e] = val;
}
}
}
}
void update(int x, int y, bool is) {
int n = x / 2;
if (is) {
if (x % 2) now[n].second |= (y + 1);
else now[n].first |= (y + 1);
}
else {
if (x % 2) now[n].second &= ~(y + 1);
else now[n].first &= ~(y + 1);
}
for (int s = 0; s < 4; s++) {
for (int e = 0; e < 4; e++) {
if ((s & now[n].first) == 0 && (e & now[n].second) == 0)
vec[n + nodeSz / 2][s][e] = base[s | now[n].first][e | now[n].second];
else vec[n + nodeSz / 2][s][e] = 0;
}
}
n += nodeSz / 2;
while (1 < n) {
n /= 2;
merge(n);
}
}
void init() {
base[0][0] = 2; base[3][0] = 1;
base[0][3] = 1; base[3][3] = 1;
base[1][1] = 1; base[2][2] = 1;
memset(vec, -1, sizeof(vec));
for (int i = nodeSz / 2; i < nodeSz / 2 + N / 2; i++)
for (int j = 0; j < 4; j++)
for (int k = 0; k < 4; k++)
vec[i][j][k] = base[j][k];
if (N % 2) {
for (int s = 0; s < 4; s++)
for (int e = 0; e < 4; e++)
vec[nodeSz / 2 + N / 2][s][e] = base[s][e];
update(N, 0, 1);
update(N, 1, 1);
}
for (int i = nodeSz / 2 - 1; i > 0; i--) merge(i);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> Q;
while (nodeSz < N / 2 + 1) nodeSz <<= 1;
nodeSz <<= 1;
init();
while (Q--) {
int a, b, c;
cin >> a >> b >> c;
if (a == 1) update(c - 1, b - 1, 1);
else update(c - 1, b - 1, 0);
cout << vec[1][0][0] << "\n";
}
}
|
c |
코드의 내용이다. 쿼리 수만큼 업데이트를 하므로 시간 복잡도는 O(QlogN), 공간 복잡도는 O(N)이다.
'알고리즘 문제풀이 공부' 카테고리의 다른 글
| 코포 일기 : Codeforces Round 909 (Div. 3) (0) | 2023.11.19 |
|---|---|
| [백준 1376] 민식우선탐색 : 세그먼트 트리의 활용 (0) | 2022.05.12 |
| 코포 일기 : Codeforces Round #733 (Div. 2) (0) | 2021.07.18 |
| 코포 일기 : Codeforces Round #726 (Div.2) (0) | 2021.07.18 |
| 코포 일기 : Codeforces Round #722 (Div. 2) (0) | 2021.05.25 |
