2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.
문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.
2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다.
[그림 1] 한 줄의 상태를 비트로 표현할 때의 정수
이 외의 경우(1010 이나 0001 등의 형태)는 나올 수 없다. 왜냐하면 "이전의 줄의 모든 칸은 채워져있다."라는 가정에서 나타나는 상태이기 때문이다. 이 가정이 성립하지 않으면 타일은 채워질 수 없다. [그림 1]에서 점은 빈 칸이고, x는 이미 타일로 채워진 칸이다 (그것이 어떠한 형태이건 채워졌다라는 상태만 의미한다.)
물론 [그림 1] 에서 1111 은 빠져있다. 필자는 1111을 0000과 동일한 상태로 봤기 때문이다. N일때 한 줄의 모든 칸이 다 차있다(1111)면 이것은 (N-1)에 대한 문제가 된다. - 자세한 것은 2N 타일링 문제 풀이 참조 - 따라서 1111 일때는 다음의 다음 칸(N-2)의 상태가 0000인 것과 같다.
그럼 한 줄의 상태로 모든 상태를 어떻게 표현하는가?
앞으로 채워야할 오른쪽의 타일에 대해 (위처럼 0000과 같이 표현된) 현재 상태로부터 진행될 수 있는 경우는 아래 그림과 같다.
[그림 2] 어떠한 상태로부터 진행될 수 있는 타일의 새로운 상태
파란색 점선 박스를 다음으로 채울 오른쪽 줄이라고 하자. 그럼 0000 으로부터 나오는 경우는 1001, 1100, 1111, 0011, 0000 과 같다. 마찬가지로 나머지 경우도 동일하다.
그렇다면 문제는 아래와 같이 쪼개어 표현이 가능하다.
f(N칸을 채우는 경우, 현재 상태) = 현재 상태로부터 만들 수 있는 다음 상태(N-1)의 개수
N이 0이 되는 순간 모든 줄을 확인했다는 의미이고 이 때의 상태가 0000(혹은 1111)이면 모든 줄을 채웠다는 의미이므로 하나의 개수로 치고, 그 외에는 잘못된 경우이다.
0000 -> 1111 -> 0000 을 한번에 넘어가는 N-2 때문에 N < 0 인 경우가 나온다. 이 때는 상태에 상관없이 불가능한 경우이므로 0 이다.
더보기
소스 코드
#include <bits/stdc++.h>
using namespace std;
int dp[501][13];
int f(int n, char bit){
if(n < 0) return 0;
if(n < 1) return bit == 0;
int& r = dp[n][bit];
if(r != -1) return r;
r = 0;
if(bit == 0){
r += f(n-1, 0);
r += f(n-1, 3);
r += f(n-1, 9);
r += f(n-1, 12);
r += f(n-2, 0);
}
if(bit == 3){
r += f(n-1, 0);
r += f(n-1, 12);
}
if(bit == 6){
r += f(n-1, 9);
}
if(bit == 9){
r += f(n-1, 0);
r += f(n-1, 6);
}
if(bit == 12){
r += f(n-1, 0);
r += f(n-1, 3);
}
return r;
}
int main(){
int t, n;
scanf("%d", &t);
memset(dp, -1, sizeof(dp));
while(t--){
scanf("%d", &n);
printf("%d\n", f(n, 0));
}
return 0;
}
댓글 3개:
아이디어 잘 얻어갑니다. 감사합니다.
잘보고 갑니다 설명이 잘되서 이해가 쏙쏙가네요 ^^7
그림이 참 좋네요 도움 많이 되었습니다!!
댓글 쓰기