[C++][DP] 백준 11727번 : 2xn 타일링 2

🏆 목차.

1. 문제
2. 코드
3. 풀이

 

🛒 문제

 

백준 11727번 2xn 타일링 2

 

🎨 코드

 

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> dp(n+1,0);
    
    dp[1] = 1;
    dp[2] = 3;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = 2*dp[i - 2] +dp[i - 1] ;
        dp[i] %= 10007;
    }
    cout << dp[n];
    return 0;
}

 

🎯 풀이

 

이번 문제는 2xn 타일링에서 살짝 변형된 다이내믹 프로그래밍(DP) 문제이다.

달리진점은 2x2 블록이 추가가 되었다는 점이고 나머지는 모두 같다.

 

2x1 블록만을 사용했을 때의 규칙은

dp [n] = dp [n-1] + dp [n-2]

이었다면

 

이번에 2x2블록이 추가됨으로써 2x1 블록 2개를 사용하는 것과 같아졌다.

그러니 2x2 공간일 때 경우의 수가 2가 아닌 3이 되는 것이다.

 

2x2타일일때 경우의수가 3이되는 모습

 

이런 규칙으로 인해 dp [i-2]를 한번 더 하는 것과 같다.

결과적으로 정답은 dp [n] = 2 * dp [n-2] - dp [n-1]이다