Tiling Problem

2013. 11. 24. 15:25알고리즘 문제풀기/DP

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


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


(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);}

'알고리즘 문제풀기 > DP' 카테고리의 다른 글

행렬을 이용한 접근  (0) 2017.01.14
APIO 2010 1번 특공대(Commando)  (0) 2015.06.30
Convex Hull Trick  (0) 2015.01.18
냅색 알고리즘  (3) 2013.12.12
Bitonic Tour  (1) 2013.11.24