11727. 2×n 타일링 2

문제링크 : https://www.acmicpc.net/problem/11727

< 입력 >

길이 n이 주어진다.

< 출력 >

2 x n 크기의 직사각형을 채우는 방법의 수 (%10,007)

< 풀이 >

계단을 1칸 2칸씩 오를 때의 경우의 수와 같은 전형적인 dp문제이다.

따라서 (2 x (n-1))의 경우와 (2 x (n-2))의 경우를 더해주면 된다.

여기서 주의해야할 점은 (2 x (n-1))의 경우를 2번 더해줘야 한다는 점이다. (즉, x 2)

이유는 2 x n 크기의 직사각형을 채울 수 있는 방법을 시뮬레이션 해보면 알 수 있다.

위 사진에서 ?가 그려진 직사각형을 2 x n 크기로 보자.

그러면 아래 그림처럼 1칸 적은 직사각형에서 2 x 1을 더하는 경우와

2칸 적은 직사각형에서 2 x 2, 1 x 2(2개) 를 더하는 경우가 있다.

a_1 = 1, a_2 = 3으로 초기화한 상태에서 a_n = a_(n-1) + (a_(n-2) * 2) 의 점화식을 세울 수 있다.

---

- 소스 코드 -

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

---