[백준] 11727번. 2×n 타일링 2 C++

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

>문제 설명

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

전에 포스팅했던 11726번. 2×n 타일링 문제를 변형한 문제이다.

밑은 가능한 타일 종류들..!

 

 

 

 

2×n 타일을 만드려면 1*2 타일은 무조건 첫 번째 그림처럼 두 개가 붙어서 나와야 한다. 따라서 2*2 타일 종류 2개, 2*1 타일 1개로 생각하면 편하다!

 

점화식을 세워보면, 11726번에 풀이했던 피보나치 식이랑 비슷하지만, 2*2 타일의 종류가 2개이므로

dp[i] = dp[i-2]*2 + dp[i-1] 이다. 

 

#define MOD 10007
#define MAXN 1001
#include <iostream>
#include <string.h>
using namespace std;

int n;
int dp[MAXN];

int main()
{
    cin>>n;
    
    dp[1] = 1;
    dp[2] = 3;
    
    for(int i=3; i<=n; i++){
        
        dp[i] = (dp[i-2]*2 + dp[i-1])%MOD;
    }
    
    cout<<dp[n]<<"\n";

    return 0;
}

 

** 주의할 점: dp[1], dp[2]는 코드에서 처럼 직접 넣어줘야 한다!