16129 - 뚜루루 뚜루
본문
최근 아기 석환이라는 노래가 큰 인기를 끌고 있다. 이 노래는 귀여운 아기 석환 캐릭터가 등장하는 동영상과 중독성 있는 뚜루루 뚜루 후렴구로 전국 각지의 학생들과 직장인들의 마음을 사로잡았다.
강남의 직장인 gs12117 역시 이 노래에 흠뻑 빠졌다. 특히 이 노래의 후렴구에 중독된 gs12117은 R줄 C칸으로 나뉘어진 종이에 뚜루루 뚜루 후렴구를 계속해서 적어 나가기 시작했다. 후렴구를 적을 때는 종이의 첫 줄 가장 왼쪽 칸에서부터 오른쪽으로 한 칸에 한 글자씩 뚜, 루, 루, 뚜, 루를 순서대로 적어 나가며, 한 줄의 가장 오른쪽 칸에 도달하면 다음 줄의 가장 왼쪽 칸으로 넘어간다.
gs12117은 이 종이에서 뚜루루 뚜루 경로를 많이 찾으려고 한다. 뚜루루 뚜루 경로란 임의의 칸에서 출발해서 이미 방문한 칸을 다시 방문하지 않도록 상하좌우로 이동하면서 각 칸에 적힌 글자를 순서대로 읽었을 때, 그 결과가 정확히 뚜루루 뚜루가 되는 경로를 말한다.
종이의 크기가 주어졌을 때, gs12117이 찾을 수 있는 뚜루루 뚜루 경로의 개수를 구하여라. 어떤 두 경로가 같은 순서에 다른 칸을 방문할 경우 두 경로는 서로 다른 경로이다.
입력
첫 줄에 종이의 줄 수와 칸 수를 의미하는 정수 $R$과 $C$ ($1 \leq R, C \leq 12117$)가 주어진다.
출력
첫 줄에 gs12117이 찾을 수 있는 뚜루루 뚜루 경로의 개수를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 0.5sec | 512MB |
풀이
간단히 생각해서, “뚜루루뚜루”가 될 수 있는 경로를 bfs를 이용해서 탐색하면 될 것 같다. 그런데, 입력으로 주어지는 grid의 크기가 최대 12117 x 12117 크기이다. 대충 1억 4천만 정도 되는 크기고, 이 칸들은 1번씩만 탐색한다고 해도 시간초과가 날 것이다. 그럼 일단 모든 칸을 탐색하는 방법으로는 풀 수 없다. 탐색 횟수를 줄여야한다.
사실 칸의 크기가 작으면 브루트포스로 모든 경우를 탐색해도 된다. “뚜”로 시작하는 위치에서 bfs를 이용해 한칸씩 이동하면서 가능한 경우를 기록해두는 것이 가능하다.
탐색 횟수를 줄이려면 어떻게 해야할까? 첫 번째 방법으로는, 중복되는 부분을 세지 않아야한다. 그런데 bfs 탐색을 전범위에서 하는 경우는 중복으로 탐색하는 부분이 없다. 이 방법으로는 탐색 횟수를 줄일 수 없다.
그럼 다음 방법으로 ‘규칙을 찾아 불필요한 계산을 줄인다’는 방법이 있다. 이 문제에 규칙이 있을까? 만약 있다면 어떻게 계산해낼 수 있을까? 예시상황을 만들어서 규칙을 찾아보자. 예시 상황은 $12 \times 12$칸이다.
| 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 |
| 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 |
| 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 |
| 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 |
| 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 |
| 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 |
| 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 |
| 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 |
| 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 |
| 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 |
| 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 |
| 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 | 루 | 뚜 | 루 | 루 | 뚜 |
문자열이 반복되는 주기는 5칸마다이다. 입력되는 것이 “뚜루루뚜루”로 반복되기 때문이다. 그렇기 때문에, 항상 5번째 열마다 같은 패턴이 반복되는 양상을 띠게 된다. 1번째 열과 6번째 열이 같고, 2번째 열과 7번째 열이 같고, … 계속해서 나아간다. 심지어 그것은 가로일 때에도 해당된다. 1번째 줄과 6번째 줄이 같고, 2번째 줄과 7번째 줄이 같다. 이것을 종합하면, 위 상황은 “5x5 크기의 칸이 반복되는 구조“임을 알 수 있다. 구역을 나눠보면 실제로 5x5 크기마다 모양이 반복되는 것을 알 수 있다. 아래 그림에서, 색칠된 부분은 같은 배열을 가지고 있다.
우리는 색칠된 하나의 구역에서 “뚜루루뚜루”가 몇개인지는 계산할 수 있다. 크기가 $5 \times 5 = 25$칸밖에 안되기 때문에 브루트포스를 통해 모든 가능한 경우를 계산해도 된다. 2차원 배열을 직접 만들수는 없으니까 탐색하려는 position을 전달해주어 그 칸이 어떤 값을 가지는지를 반환하도록 하자. 그러면 배열을 모두 저장할 필요 없이 $x, y$값만으로도 그 칸이 ‘뚜’인지 ‘루’인지 알아내도록 할 수 있다. 그 이후 ‘뚜’부터 시작하여 “뚜루루뚜루” 경우의 개수는 브루트포스를 통해 계산할 수 있다. 이건 미리 계산해서 기록해두자.
그리고 그 결과를 여러번 더해서 계산하면 될 것 같다. 위 그림에서, 5x5 크기의 구역이 총 4개이므로 색칠된 구역의 총합은 $4 \times ([5 \times 5])$가 될 것 같다. 하지만 그렇지 않다. 이 문제를 푸는 핵심으로, 단순히 구역을 나누고 그 결과를 곱한다고 해서 끝나지 않는 문제다.
사실 5x5 크기의 구역에서 경우의 수를 구했다는 것은, 다시 얘기하면 “그 구역 안에서만 가능한 경우의 수”를 의미한다. 근데, 위 그림에서는 구역 내에서의 경우 말고도 다른 경우들이 존재할 수 있다. 아래는 그 리스트다.
- 2개 구역을 모두 사용하는 경우
- 노랑 - 회색
- 노랑 - 하늘
- 회색 - 주황
- 하늘 - 주황
- 4개 구역을 사용하는 경우
그래서, 위 그림에서는 색깔이 칠해진 구역이 4개인 것처럼 보이지만, 사실 구역을 9개로 보아야한다는 시점이 있어야 한다. 색칠된 각 구역, 2개 구역 사이의 선, 4개 구역 사이의 꼭짓점으로 총 9개라고 보면 이후를 계산하기 쉬워진다.
하얀색 글씨가 써진 칸들은 노란색 칸들과 조합이 되지 않는다. 따라서, 노란색 구역과 연계하여 “뚜루루뚜루”를 만들 수 있는 칸들은 색칠된 칸들이 유일하고, 그 경우의 수에는 규칙이 없다. 따라서, 우리는 1x1 크기부터 10x10 크기까지의 경우의 수를 미리 모두 계산하여 기록해두면, 그 값들을 이용하여 전체 경우의 수를 규칙을 이용하여 계산할 수 있다.
각각의 기본형들을 계산하여 기록하였으면, 그 결과를 합치면 된다. 구역을 나눠보면 아래 리스트와 같을 것이다.
5x5 구역 + 다른 블럭들과의 접점을 모두 포함하는 블럭 (빨간색 상황)
![p3]()
5x(가로) 구역 + 아래 블럭들과의 접점을 모두 포함하는 블럭 (옅은 빨간색 상황)
![p4]()
(세로)x5 구역 + 오른쪽 블럭들과의 접점을 모두 포함하는 블럭 (하늘색 상황)
![p5]()
마지막 남은 블럭 (회색 상황)
![p6]()
마지막 그림으로 보면, 모든 칸을 칠한 것을 알 수 있다. 즉, 위의 경우들을 모두 더하기만 하면 우리가 원하는 답을 찾아낼 수 있다는 의미이다!
각 경우가 몇번 나오는지를 계산해내면, 간단한 수식으로 계산할 수 있게 된다. 생각해보면 각 구역은 5칸을 기준으로 삼고 있다는 것을 알 수 있다. 예시로 하늘색 구역을 보면, 전체 grid에서는 필연적으로 나머지가 생기게 되는데 ($12 \% 5 = 2 $), 그 나머지만 하나의 구역으로 두는 것이 아니라 거기에 5x5 크기의 구역을 하나 포함하여 두는 것을 볼 수 있다. 이는 우리가 이미 10x10 크기까지의 구역을 모두 계산해두었기 때문에, 저 구역을 2개로 분할하지 않고 한번에 계산하는게 편하기 때문이다. 그것을 기억하고 각 구역의 개수를 어떻게 계산할지 생각해보자.
총 칸이 $r \times c$칸이라면, 그 칸들은 세로 5x5 크기의 블럭이 총 $r // 5$개, 가로 5x5 크기의 블럭이 총 $c//5$개 있을 것이다. 그런데 나머지 블럭의 핸들링을 위해 5x5 크기의 블럭을 한개씩 빼서 사용할 것이므로, 실질적으로 5x5 크기의 블럭으로 쓰는 것들의 개수는 각각 $r // 5 - 1$, $c // 5 - 1$개이다. 그리고, 구역의 개수는 $0$보다 작을 수 없으므로, 저 값들이 음수라면 5x5 크기의 구역이 없다는 것으로 받아들일 수 있다. 이들을 각각 $a_r, a_c$라고 표현하겠다. 즉, $a_r = \max(r//5-1, 0)$, $a_c = \max(c//5-1, 0)$이다. 이를 이용하여 각 블럭의 개수를 알아보자.
- 5x5 구역 + 다른 블럭들과의 접점을 모두 포함하는 블럭 (빨간색 상황)
- 계산하는 방법 : $10 \times 10 - 5 \times 10 - 10 \times 5 + 5 \times 5$ (직접 구역을 색칠해보며 차집합, 합집합 연산해보면 알 수 있다)
- 존재하는 개수 : $a_r \times a_c$ (가장 아래 또는 가장 오른쪽의 5x5 구역은 빼야하므로 이 개수만큼 빨간색 구역으로 사용 가능하다)
- 5x(가로) 구역 + 아래 블럭들과의 접점을 모두 포함하는 블럭 (옅은 빨간색 상황)
- 계산하는 방법 : $10 \times (5+x_1) - 5 \times (5+x_1)$
- 존재하는 개수 : $a_r$ (세로 개수만큼 존재할 수 있다)
- (세로)x5 구역 + 오른쪽 블럭들과의 접점을 모두 포함하는 블럭 (하늘색 상황)
- 계산하는 방법 : $(5+x_2) \times 10 - (5+x_2) \times 5$
- 존재하는 개수 : $a_c$ (가로 개수만큼 존재할 수 있다)
- 마지막 남은 블럭 (회색 상황)
- 계산하는 방법 : $(5+x_1) \times (5+x_2)$
- 존재하는 개수 : 단 1개만 존재한다
이제, 위 값들을 전부 더하면 문제의 답을 구할 수 있게 된다. 나머지는 직접 구현해보자!
- 참고 알고리즘 : 브루트포스
코드
사용 언어 : C
최종 수정일 : 2023 / 3 / 4
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef long long ll;
typedef struct Node {
int x, y;
} ND;
#define STD 5
bool isDDu[STD] = {true, false, false, true, false};
int r, c;
ll dp[STD * 2 + 1][STD * 2 + 1];
#define DIR 4
ND dir[DIR] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
typedef struct QueueNode {
ND pos;
int cnt;
ND vis[STD];
} QN;
#define MAX_IDX ((STD * 2) * (STD * 2) * STD + 1)
ll getSubResult(int maxR, int maxC, ND start) {
QN q[MAX_IDX];
int f = 0, r = 0;
q[r++] = (QN){start, 1, {start}};
ll ret = 0;
while (f < r) {
QN cur = q[f++];
if (cur.cnt == STD) {
++ret;
continue;
}
for (int i = 0; i < DIR; ++i) {
ND next = (ND){cur.pos.x + dir[i].x, cur.pos.y + dir[i].y};
bool isVisited = false;
for (int j = 0; j < cur.cnt; ++j) {
if (next.x == cur.vis[j].x && next.y == cur.vis[j].y) {
isVisited = true;
break;
}
}
if (isVisited == false && next.x >= 0 && next.x < maxR && next.y >= 0 && next.y < maxC) {
if (isDDu[(next.x * c + next.y) % STD] == isDDu[cur.cnt]) {
q[r].pos = next, q[r].cnt = cur.cnt + 1;
for (int j = 0; j < cur.cnt; ++j) {
q[r].vis[j] = cur.vis[j];
}
q[r++].vis[cur.cnt] = next;
}
}
}
}
return ret;
}
#define min(a, b) (((a) > (b)) ? (b) : (a))
#define max(a, b) (((a) > (b)) ? (a) : (b))
void init() {
for (int i = 1; i <= min(r, STD * 2); ++i) {
for (int j = 1; j <= min(c, STD * 2); ++j) {
ll ret = 0;
for (int a = 0; a < i; ++a) {
for (int b = 0; b < j; ++b) {
if (isDDu[(a * c + b) % STD] == true) {
ret += getSubResult(i, j, (ND){a, b});
}
}
}
dp[i][j] = ret;
}
}
return;
}
void print_result() {
ll ret = 0;
int squR = max(0, (r - STD) / STD), squC = max(0, (c - STD) / STD);
r -= (squR * STD), c -= (squC * STD);
ret += ((squR * squC) * (dp[STD * 2][STD * 2] - dp[STD * 2][STD] - dp[STD][STD * 2] + dp[STD][STD]));
ret += ((squR) * (dp[STD * 2][c] - dp[STD][c]));
ret += ((squC) * (dp[r][STD * 2] - dp[r][STD]));
ret += dp[r][c];
printf("%lld", ret);
return;
}
int main() {
scanf("%d %d", &r, &c);
init();
print_result();
return 0;
}
dp[][]: 1x1 크기부터 10x10 크기까지의 구역 안에서의 경우의 수를 기록