16201 - 발코니 공사
본문
앨버트는 공구점을 운영하는 친구로부터 1×2 크기의 타일을 매우 많이 받았다. 이 타일은 아래와 같이 가로로 긴 직사각형 형태이며, 두 개의 정사각형 칸이 ‘두 개’ 이어 붙여져 있다.
마침 별장의 정원 발코니 바닥이 부서져서 수리하려던 참이라, 얻은 타일을 이용해 빈 공간을 채우려고 한다. 정원 발코니 바닥은 직사각형 모양이고, $R$×$C$개의 정사각형 칸으로 나누어져 있다. 아래 그림은 $R = 4, C = 5$인 경우이다. 1×2 타일을 이용하면 좌우로 인접한 두 칸을 완전히 덮어서 채울 수 있지만, 타일을 회전해서 상하 두 칸을 덮을 수는 없다.
칠해져 있는 칸은 부서지지 않은 칸, 칠해져 있지 않은 칸은 부서진 칸이다. 위의 그림에서는 6개의 칸이 부서지지 않은 칸, 14개의 칸은 부서진 칸이다.
이제, 부서진 칸을 1×2 크기의 타일만 가지고 채워 넣어야 한다. 크기가 1×2이기 때문에, 모든 칸을 채울 수 없을 수도 있지만, 최대한 많은 칸에 타일을 채워 넣으려고 한다.
타일은 부서진 칸 두 칸을 모두 덮어야 하고, 두 타일이 겹치면 안 된다. 또한, 발코니의 경계선을 넘어가도 안되고, 부서지지 않은 칸을 덮어도 안 된다.
위의 그림의 경우에 6개의 타일을 이용해서 부서진 칸을 최대한 많이 채울 수 있다. 모든 타일은 똑같이 생겨서 구분되지 않지만, 편의상 번호를 붙여 구분했다.
또 다른 두 가지 방법으로 아래와 같이 채우는 것도 가능하다.
별장 발코니 바닥을 채울 수 있는 방법의 수를 구하는 프로그램을 작성하시오. 두 방법이 있을 때, 적어도 한 칸에 대해서 한 방법에선 타일로 채웠고, 다른 방법에선 채우지 않은 경우가 있다면, 두 방법은 다른 방법이라고 한다.
입력
첫째 줄에 별장 발코니의 크기 $R, C$와 부서지지 않은 칸의 개수 $K$가 주어진다. ($1 ≤ R ≤ 1\,000\,000\,000, 2 ≤ C ≤ 1\,000\,000\,000, 0 ≤ K ≤ 1\,000$)
둘째 줄부터 $K$개의 줄에는 부서지지 않은 칸의 위치가 공백으로 구분해 주어진다. 위치는 행과 열의 번호로 나타낸다. 행은 $1$부터 $R$까지, 열은 $1$부터 $C$까지이다. 똑같은 위치가 여러 번 주어지는 경우는 없다.
적어도 하나의 타일을 놓을 수 있는 경우만 주어진다.
출력
총 두 개의 수를 출력해야 한다. 첫 번째 수는 가장 많은 타일을 사용한 경우에 사용된 타일의 수, 두 번째 수는 그때 방법의 수이다. 단, 방법의 수가 매우 클 수 있기 때문에, $1\,000\,000\,007$로 나눈 나머지를 출력한다. 타일의 수는 항상 $10^{18}$이하이기 때문에, 나누지 않아야 한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 512MB |
풀이
타일의 모양이 1x2 크기고 돌릴 수 없다는 점이 계산을 더 쉽게 해준다고 생각한다. 타일을 세로로 설치할 수 없으므로 가로줄 하나만 고려하면 되고, 그것도 2가지 case만을 고려하면 되기 때문이다.
- 현재 계산하고 있는 비어있는 칸이 홀수개 존재하는 경우
- 현재 계산하고 있는 비어있는 칸이 짝수개 존재하는 경우
짝수칸을 고려하고 있다면 할 수 있는 방법은 빈 칸을 전부 덮어버리는 경우밖에 없다. 이 때 사용하는 타일의 개수는 비어있는 칸의 절반, 그걸 덮는 경우의 수는 $1$가지밖에 없다.
홀수칸을 고려하고 있다면 계산이 달라진다. 어떻게 타일을 설치하더라도 빈칸이 1개 남아버린다. 타일의 개수는 $\lfloor N/2 \rfloor$개, 그걸 덮는 경우의 수는 $(N+1)/2$개 존재할 수 있다.
그리고 이 과정을 모든 줄에 대해서 계산하면 된다. 다른 줄은 서로 간섭되지 않으므로 case를 나누어서 풀어내면 된다.
- 현재 줄에 막힌 칸이 없는 경우 (하나의 줄을 하나의 그룹으로 묶어서 생각할 수 있다)
- 현재 줄에 막힌 칸이 있는 경우 (각각 나뉘어지는 부분을 그룹으로 묶어서 생각한다)
다만 문제에서 주어질 수 있는 줄이 최대 10억까지다. 전부 나누는 것은 불가능하다.
다행히도, 막힌 칸의 개수는 최대 1000개이다. 그렇다면 최대 1000줄에서만 막히는 경우가 존재하고, 그 이외는 전부 비어있는 줄이라는 것을 알 수 있다. 비어있는 줄에 대한 계산은 항상 같은 결과만 나오므로 하나하나 계산하지 않고 한번에 묶어서 결론을 도출할 수 있다.
각각 어떤 부분으로 나뉘어지는지, 그 때의 결과가 무엇인지, 한번에 몇개의 줄을 계산할 것인지 만 잘 계산해주고 그 결과를 전부 곱해서 합칠 수 있다면 해결할 수 있는 문제.
- 참고 알고리즘 :
코드
사용 언어 : C
최종 수정일 : 2023 / 4 / 13
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
#include <stdio.h>
typedef long long ll;
typedef struct Node {
ll x, y;
} ND;
const ll MOD = (ll)(1e9 + 7);
ll r, c;
#define MAX_IDX 1000
ND arr[MAX_IDX + 1];
int k;
ll tile = 0, method = 1;
int cmp(ND* a, ND* b) {
if (a->x == b->x) {
return a->y > b->y;
} else {
return a->x > b->x;
}
}
ll power(ll a, ll b) {
if (b == 0) {
return 1;
} else if (b == 1) {
return a % MOD;
} else {
ll x = power((a * a) % MOD, b / 2);
if (b % 2 == 1) {
x = (x * a) % MOD;
}
return x % MOD;
}
}
void addLineResult(ll x) {
tile += (x * (c / 2));
if (c % 2 == 1) {
method *= power((c + 1) / 2, x);
method %= MOD;
}
return;
}
void addPartResult(ll x) {
if (x > 1) {
tile += (x / 2);
if (x % 2 == 1) {
method *= ((x + 1) / 2);
method %= MOD;
}
}
return;
}
int main() {
scanf("%lld %lld %d", &r, &c, &k);
for (int i = 0; i < k; ++i) {
ll a, b;
scanf("%lld %lld", &a, &b);
arr[i] = (ND){a, b};
}
arr[k] = (ND){r + 1, 0};
if (k == 0) {
addLineResult(r);
} else {
qsort(arr, k + 1, sizeof(ND), cmp);
ND pre = (ND){1, 0};
for (int i = 0; i < k + 1; ++i) {
ND cur = arr[i];
if (cur.x > pre.x && pre.y > 0) {
addPartResult(c - pre.y);
pre = (ND){pre.x + 1, 0};
}
if (cur.x > pre.x) {
addLineResult(cur.x - pre.x);
pre = (ND){cur.x, 0};
}
if (cur.y > pre.y) {
addPartResult(cur.y - pre.y - 1);
}
pre = cur;
}
}
printf("%lld %lld", tile, method % MOD);
return 0;
}