BOJ 백준 11727 2xN 타일링 2

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

11727번: 2×n 타일링 2

 

2xN 타일링

https://onecoke.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-11726-2xN-%ED%83%80%EC%9D%BC%EB%A7%81

BOJ 백준 11726 2xN 타일링

 

문제 풀이)

 

    2xN 타일을 채우는 백준 11726과 같은 방법으로 풀면 되는 문제이다.

 

    문제는 2xN 직사각형을 2x1과 2x2 타일로 채우는 방법의 수이지만, 예제에는 1x2 타일도 사용되고 있으므로

 

    1x2 타일도 고려해주어야 한다.

 

    이 문제 또한 길이가 1로 끝나는 경우와 2로 끝나는 두 가지 경우가 존재한다. 하지만, 타일링 1번 문제와 다른점은

 

    길이가 2인 경우에 1가지 방법이 아닌 2가지 경우가 존재한다.

    3가지로 보이겠지만, 타일링 1번을 이해했다면 위의 방법은 2가지라는 것을 알 수 있을 것이다.

 

    첫 번째 1x2 타일 2개로 채워진 경우는, 길이가 1로 끝나는 경우( 1x2 타일 한 개로 채워지는 경우 ) 와 같다.

 

        1. 길이가 1 남고 1x2 타일 한 개로 채우는 경우        => 길이 n - 1의 타일을 채우는 경우

 

        2. 길이가 2 남고 2x1 타일 두 개로 채우는 경우        => 길이 n - 2의 타일을 채우는 경우

 

        3. 길이가 2 남고 2x2 타일 한 개로 채우는 경우        => 길이 n - 2의 타일을 채우는 경우

 

    따라서 길이 n의 타일을 채우는 방법의 수는 n - 1개의 타일을 채우는 경우의 수 +

    (n - 2)개의 타일을 채우는 경우의 수 * 2 가 된다.

 

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

 

소스 코드

#include <cstdio>
#define MOD 10007

using namespace std;

const int SIZE = 1010;
int n;
int dp[SIZE] = { 0 };

int main()
{
	scanf("%d", &n);
	dp[0] = 1;
	dp[1] = 3;

	for (int i = 2; i < n; ++i)
		dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % MOD;

	printf("%d\n", dp[n - 1]);
	
	return 0;
}