[알고스팟/ALGOSPOT] 17. TILING2

고라파덕!

이번 문제는 TILING2라는 문제입니다. 이 문제는 동적계획법을 알아가는 문제 중 한 문제라 생각합니다. 마치 계단오르기 같이 점화식을 유추하기 쉬운 문제입니다. 

TILING2 문제 (출처 : https://algospot.com/judge/problem/read/TILING2)

문제

2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.

예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다.

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

입력

입력의 첫 줄에는 테스트 케이스의 수(C <= 50)가 주어집니다. 그후 C줄에 각각 1개의 자연수로 n(1 <= n <= 100)이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 경우의 수를 1000000007로 나눈 나머지를 출력합니다.

예제 입력

3
1
5
100

예제 출력

1
8
782204094

노트

문제는 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 방법의 수를 구하는 문제입니다. 

예를 들어 사각형이 2X4의 사각형이라면

ㅣㅣㅣㅣ, ㅣㅣ-, ㅣ-ㅣ, -ㅣㅣ, -- 이렇게 5가지의 종류가 나오겠죠!

그럼 여기서 우리는 어떻게 저런 방법이 생기는지 알아보면 됩니다. 

N크기의 사각형을 채우려면 항상 N-1크기의 사각형에서 ㅣ하나를 추가시키면 되고, N-2크기의 사각형에서 - 하나를 추가시킬 수 있습니다.

그렇기 때문에 N-1의 방법의 개수 + N-2의 방법의 개수라는 식이 나오게 됩니다. 

TILING2(point) = TILING2(point -1) + TILING2(point - 2) 이런 점화식이 나오게 되죠.

배열로 나타내면

1 2 3 5 8 13 ... 피보나치의 수가 됩니다.

#include <iostream>

using namespace std;

void INPUT(); // INPUT 함수

long long int TILING(int point); // 동적계획법 함수

long long int cache[110]; // 메모이제이션 배열

int N; 

int main()

{

int testcase;

scanf("%d", &testcase); // 테스트 케이스 입력

while(testcase >= 1)

{

--testcase;

INPUT();

}

return 0;

}

void INPUT()

{

scanf("%d", &N); // N입력

for(int i=0; i<=N; i++) cache[i] = -1; // 메모이제이션 배열을 -1(초기값)으로 초기화

printf("%d\n", TILING(0)); // 동적계획법시작

}

long long int TILING(int point)

{

long long int &ret = cache[point]; // 현재 상태의 메모이제이션

if(ret != -1) return ret; // 기억해둔 것이 있다면 기억해둔것을 반환;

if(point > N) return 0; // 타일링 크기를 넘어간다면

else if(point == N) return 1; // 딱맞으면 한개

ret = TILING(point + 1) + TILING(point + 2); // 점화식

if(ret > 1000000007) ret %= 1000000007; // 문제 조건

return ret;

}