8.12문제: 비대칭 타일링(ID:ASYMTILING)
문제
그림과 같이 2 n 크기의 직사각형을 2 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 좌우 대칭이어서는 안 됩니다. 위 그림은 2 * 5 크기의 직사각형을 채우는 비대칭 타일링 방법 6가지를 보여줍니다. 다음의 2가지는 좌우대칭이기 때문에 세지 않습니다.
n 이 주어질 때 가능한 비대칭 타일링 방법의 수를 계산하는 프로그램을 작성하세요. 방법의 수는 매우 클 수 있으므로, 1,000,000,007 로 나눈 나머지를 출력합니다.입력
입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 그 후 각 줄에 사각형의 너비 n (1 <= n <= 100) 이 주어집니다.
출력
각 테스트 케이스마다 한 줄에 비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지를 출력합니다.
예제 입력
3 2 4 92예제 출력
0 2 913227494
First Thoughts
대칭이 되는 경우
일단 앞에 예제 "타일링 방법의 수 세기(tiling2)"를 참고하여 타일을 채우는 방법의 수를 계산할 수 있다. 모든 경우의 수에서 비대칭적인 경우만 세야하는데 n=2부터 5까지 해보니 대칭적인 타일을 제거하는 방법이 효율적이겠다. 대칭적인 경우는 크게 세가지인거 같다.
i) 가운데에 세로방향으로 채워진 하나의 타일을 기준으로 대칭적인 모습
ii) 가운데에 가로방향으로 채워진 두개의 타일을 기준으로 대칭적인 모습
iii) 가운데 기준으로 대칭적인 타일을 기준으로 대칭적인 모습
첫 번째 경우는 너비가 홀수일 때이고 두번째와 세번째 경우는 너비가 짝수일 때의 모습이다. 이를 염두해두고 코드를 작성해보자.
My Code
#include <iostream>
#include <cstring>
using namespace std;
const int MOD=1000000007;
int cache[101];
int tiling(int n) {
if (n <= 1)
return 1;
int& ret = cache[n];
if (ret != -1)
return ret;
else
return ret = (tiling(n - 2) + tiling(n - 1))%MOD;
}
int tile(int n) {
int t;
if (n % 2 == 1)//홀수일 경우
return (tiling(n) - tiling((n - 1) / 2) + MOD) % MOD;
else//짝수일 경우
{
t = (tiling(n) - tiling(n / 2) + MOD) % MOD;
t = (t - tiling(n / 2 - 1) + MOD) % MOD;
return t;
}
}
int main(void) {
int C;
int i;
int n;
cin >> C;
memset(cache, -1, sizeof(cache));
for (i = 0; i < C; i++) {
cin >> n;
cout << tile(n) << endl;
}
}Answer Code
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1000000007;
int cache[101];
int tiling(int n) {
if (n <= 1)
return 1;
int& ret = cache[n];
if (ret != -1)
return ret;
else
return ret = (tiling(n - 2) + tiling(n - 1))%MOD;
}
int asymmetric(int width) {
if (width % 2 == 1)
return (tiling(width) - tiling(width / 2) + MOD) % MOD;
int ret = tiling(width);
ret = (ret - tiling(width / 2) + MOD) % MOD;
ret = (ret - tiling(width / 2 - 1) + MOD) % MOD;
return ret;
}
int main() {
int C;
int n;
cin >> C;
memset(cache, -1, sizeof(cache));
for (int i = 0; i < C; i++) {
cin >> n;
cout << asymmetric(n) << endl;
}
}Difference & Faults
음수일 때 고려
cache에 저장되는 값은 양수이겠지만 대칭되는 부분을 빼다보면 음수가 나올 수 있다. 이 음수의 나머지를 구하기 위해서 나누는 수를 더해 양수로 만든 다음 나눈다는 것을 잊지 말자. 특히 짝수일 경우 두 가지 경우를 생각해야되는데 이때 한 가지 경우만 제거해도 음수가 될 수 있기 때문에 각 방법을 따로따로 나누어 계산하거나 한꺼번에 빼서 MOD를 2번 더해주면 답을 구할 수 있다.
cache[n]의 사용
cache의 값을 참조할 때 인데스값을 너비의 길이인 n 그대로 사용하였다. 그래서 cache[0]일 때를 사용하지 않아 n이 최대일때를 대비해 cache의 최대를 101까지로 설정해야한다.
Impressions
책에서는 비대칭 타일을 계산하는 방법으로 '대칭되는 타일 빼기','비대칭 타일만 세기'가 있다. 앞에 제시한 코드는 대칭되는 타일을 빼는 방법인데 비대칭 타일을 직접 계산하는 코드도 배울 점이 많다. 경우의 수 문제답게 이 역시 각 패턴별로 지녀야할 속성을 잘 고려하여 비대칭인 경우만 선별하여 계산하였다.
Summary
이번 문제 역시 앞에서 푼 문제의 응용이라 크게 어렵진 않았다. 다만 대칭되는 패턴을 생각해보고 각 패턴별 특징을 통해 코드를 작성하는 과정에서 번거러움이 있었다. 항상 사소한 거에도 유의해야되니는 습관을 기를 필요가 있다.
