Tiling Problem

간단한 다이나믹 문제에서 최소한의 메모리만을 사용할 수 있는 기법을 설명하는 글이다.

일단 기반이 되는 문제는 이러하다.

(Algospot : TILING2)

문제

2×n 크기의 사각형을 2×1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. (1 <= n <= 100)

경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.

예제 입력 1

5

예제 출력 1

8

예제 입력 2

100

예제 출력 2

782204094

유명한 다이나믹 문제이다.

2×n의 타일을 채우는 방법에서, 제일 오른쪽 타일을 보자.

┌─┐　　　　┌┐
├─┤　　　　││

└─┘　　　　└┘

두 가지의 채우는 방법이 있다.

첫 번째 경우로 채우는 방법의 수는, 2×(n-2) 까지의 타일을 채우는 방법의 수와 일치하고,

두 번째 경우로 채우는 방법의 수는, 2×(n-1) 까지의 타일을 채우는 방법의 수와 일치한다.

따라서 a[n]=(2×n까지의 타일을 채우는 방법의 수)라고 하면

a[n]=a[n-1]+a[n-2];

또한 초기값은 a[0]=1, a[1]=1이다.

#include <cstdio>
int main() {
    int n;
    int a[101]; a[0]=1; a[1]=1;
    int i;
    for(i=2;i<=100;i++) a[i]=a[i-1]+a[i-2];
    scanf("%d",&n); printf("%d",a[n]);
    return 0;
}

이 문제에는 여러 가지 변형이 있다.

1) 2x1, 1x1 타일이 있는 경우 - koistudy 타일채우기II(Small)

여기서 n ≤ 10,000,000

여기서 배열 하나로 생각하면 꽤 복잡하다.

a[i]    = 2×i을 꽉 채우는 방법

b[i]    = 2×i를 오른쪽 위 꼭짓점이 비어있는 채로 채우는 방법

= 2×i를 오른쪽 아래 꼭짓점이 비어있는 채로 채우는 방법(대칭이므로)

이렇게 선언해 주면 점화식이 나온다.

역시 제일 오른쪽 부분을 생각해 보면,

a[i] = a[i-2] // 가로로 도미노 두 개가 놓인 경우

+ a[i-1] // 세로로 도미노 하나가 놓인 경우

+ a[i-1] // 모노미노 두 개가 세로로 놓인 경우

+ b[i-1] // 위쪽에 모노미노 한개, 아랫쪽에 도미노 한개 가로로 놓인 경우

+ b[i-1]; // 위쪽에 도미노 한개 가로로, 아랫쪽에 모노미노 한개 놓인 경우

b[i] = a[i-1] // a[i-1]의 오른쪽 끝에 모노미노 한 개를 놓는 방법

+b[i-1]; // b[i-1]의 비어있는 부분에 도미노를 가로로 놓는 방법

전역변수로 a[10000000]; 하고 잡으면 컴파일이 잘 안되거나(힙 제한),

지역변수로 a[10000000]; 하고 잡거나 동적 할당하면 선언에 실패한다(스택 제한).

10000000개짜리 int배열 2개를 잡으면 이 배열만 해도 76MB의 메모리를 차지하기 때문.

그렇다면...?

여기서 a나 b를 구할 때, a[i]에서 a[i-3]을 참조하는 일은 없다.

즉 다이나믹에서는 참조할 값만큼만 들고 있으면 된다.

그러므로 a[3], b[3]만 선언한 후, 

① a[2]와 b[2]를 구하고,

② a[0]=a[1]; a[1]=a[2];

③ b[0]=b[1]; b[1]=b[2];

이것을 (n-1)번 반복하고 a[1]을 출력해주면 되겠지.

#import<cstdio>
main(){int x,a=1,b=2,c,e=1,f,g=0xf4240;scanf("%d",&x);for(x--;x--;){c=((b+e)<<1)+a;a=b;f=b+e;e=f%g;b=c%g;};printf("%d",b);}