[백준 11727] 2×n 타일링 2

🔗알고리즘 문제

오랜만에 풀어본 DP문제이다. 오랜만에 푼 만큼 해결방법이 잘 생각나지 않아서 힘들었던 문제이다.

문제 분석

이 문제는 사진에 나온것처럼 2*n의 직사각형을 1x2 2x1 2x2 3개의 도형을 이용해서 채우려할 때 몇가지 경우가 생기는지를 알아내는 문제이다.

발상 & 알고리즘 설계

2×n 타일링 문제에서 2x2블럭의 존재 하나만 추가해주면 되는 간단한 문제이다.

직사각형의 세로 칸을 1이라고 생각하고 본다면 모든 블럭의 너비는 1아니면 2이다. 이 때 너비 2의 칸에는 2x1블럭과 2x2블럭 두개가 들어갈 수 있으므로 arr[i-1] + arr[i-2] * 2 라는 점화식이 성립하게 된다.

코드

#include<iostream>

using namespace std;


int main(){
    int dp[1001] = { 0, 1, 3 };
    int n;

    cin >> n;

    for(int i = 3; i <= n; i++){
        dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
    }

    cout << dp[n];
}