[C++] 백준 - 11727 : 2 x n 타일링 2

문제 링크

11727번: 2×n 타일링 2

 

풀이 ) DP

  앞문 제인 2 x n 타일링과 다른 점은 시작하는 방법이 하나 추가됐다는 점이다.

  2 x 1 타일로 시작할 수 있고 이 때는 뒤에 2 x (n-1) 직사각형을 채우면 되고

  1 x 2 타일 2개로 시작하거나 2 x 2 타일로 시작하는 경우는 뒤에 2 x (n-2) 직사각형을 채우면 된다.

  따라서 점화식은 memo[n] = memo[n-1] + 2 * memo[n-2]이다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1002] = {0, 1, 3, };

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 3; i <= n; ++i)
        memo[i] = (memo[i-1] + memo[i-2]*2)%10007;
    printf("%d\n", memo[n]);
    return 0;
}

 

주의점 )

  앞 문제와 같이 모듈러 연산은 for문에서 한다.