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

문제 링크

11726번: 2×n 타일링

 

 

풀이 ) DP

  직사각형의 첫 타일이 2 x 1인 경우와 1 x 2 2개로 시작하는 2가지 경우로 나눌 수 있다.

  2 x 1로 시작하는 경우 뒤에 2 x (n-1) 직사각형을 채우면 되고

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

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

 

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

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

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

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

 

주의점 )

  memo[n]을 구하는 과정에서 모듈러 연산을 해줘야지 정수 오버플로우가 발생하지 않는다.