[백준 11727번] 2xn 타일링 2

풀이

---

2xn 타일링 문제에서 타일이 하나더 늘어난 형태의 문제다.

2xn 타일링 문제를 풀때와 동일하게 DP를 이용하고 DP배열의 크기를 크게 잡아주어야 한다.

다만 타일이 하나가 더늘어 났기때문에 점화식을 수정해주어야한다.

1x2, 2x1, 2x2 타일로 채우는 경우의 수를 구할 때 가로 크기가 2인 타일이 하나가 더추가되었다.

i번째 타일의 경우는 i-1번째에서 1x2짜리 타일 한개붙이는 경우와 i-2번째에서 2x1 타일 두개 붙이는 경우와 2x2 타일 한개를 붙이는 경우가 있다.

즉, dp[i] = dp[i-1] + dp[i-2]*2 을 도출할 수 있다.

소스 코드

---

#include <iostream>
using namespace std;
 
int n;
long long dp[1001];
 
int main() {
    cin >> n;
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]*2)%10007;
    }
    cout << dp[n] << '\n';
    return 0;
}