[11727번] 2xn 타일링 2

문제 출처 :

https://www.acmicpc.net/problem/11727

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 경우의 수

타일링 문제에서 타일이 총 3가지가 주어졌다.

아래의 파란 부분을 마지막으로 채우기 위해서는 앞에서 어떤 작업이 이루어 져야할지 생각해 봐야한다.

첫번째 세로로 긴 타일 한장을 놓는 경우를 보자.

빨간 동그라미 부분은 어떻게 쌓여오든 관계없다 생각하고 세로로 긴 타일을 한장 놓고, 마무리를 하면된다.

이 과정은 곧 DP[i-1]이 될 것이다.

그리고 그 2번째, 3번째 그림을 보면 두칸 전부터 해결하고 있다.

두칸 전부터 정사각형을 하나 놓으면 되고, 아니면 가로로 긴 타일을 2장 놓으면 된다.

즉, 이 과정은 DP[i-2] * 2가 될것이다. 

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <iostream> #include <cstring>   using namespace std;   int main() {       int n, i;     long long int dp[1001];       dp[0] = 1;     dp[1] = 1;     dp[2] = 3;       scanf("%d", &n);       for (i = 3; i <= n; i++)     {         dp[i] = (dp[i-1] + dp[i - 2]*2) % 10007;     }     printf("%lld", dp[n]);   }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocu