백준(BOJ) 11726번 2xn 타일링

문제 : https://www.acmicpc.net/problem/11726

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

나의풀이 :

세로줄 왼쪽부터 채워나갈수 있는 경우의 수를 생각해보자. 세로로 한개, 가로로 두개 두 경우 이외에는 없기 때문에

재귀적으로 구현해주고 n이 1000까지 있기에 완전 탐색으로는 시간 내에 불가능하니 메모이제이션을 적용해서 중복되는 탐색을 방지하자.

코드 ( C ++ )

#include <iostream>

#include <cstring>

using namespace std;

int N;

const int MAX = 1000;

int cache[MAX+1];  // n이 1000일 경우 cache[1000]이 필요하기에 [0~999]에 1 추가

int tiling(int n)

{

if (n <= 1) return 1;

int& ret = cache[n];   // n일때의 방법의 수를 이미 안다면 다시 계산하지 않고 캐쉬에 저장된 배열 이용  

if (ret != -1) 

return ret;

return ret = (tiling(n - 1) + tiling(n - 2))%10007;  // 어떻게 덮었는지는 상관없고 덮는 방법은 오직 두가지 뿐 

}

int main()

{

cin >> N;

memset(cache, -1, sizeof(cache));  //  메모이제이션을 위한 cache -1로 초기화

int result = tiling(N);

cout << result << endl;

return 0;

}