[C++] 백준 11726번 - 2×n 타일링

---

0. 문제

 

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

1. 아이디어

 

1) 기본 단위를 1x2 타일, 그리고 2x1 타일이 위아래로 붙어있는 모양. 이렇게 나눈다.

 

2) 길이가 n인 직사각형을 채우는 방법은, n-1인 직사각형에 1x2타일을 붙이는 방법 and n-2인 직사각형에 2x1 타일이 위아래로 붙어있는 모양을 붙이는 방법. 이렇게 구분하면 DP를 이용해 구현할 수 있다.

 

2. 소스코드

 

#include <iostream>
int main()
{
    int n,result;
    std::cin >> n;
    if (n == 1) result = 1;
    else if (n == 2) result = 2;
    else
    {
        int* dp = new int[n + 1];
        dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++)
            dp[i] = (dp[i - 1] + dp[i - 2])%10007;
        result = dp[n];
        delete[] dp;
    }
    std::cout << result;
}

 

3. 결과

 

4. 피드백

 

• dp[i]에 가능한 방법의 수를 저장한 후 출력할 때 10007로 나눈 나머지를 출력하려다 보니까 오버플로우가 났다.

---