[백준] 2xn 타일링 2 (11727번)

문제

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

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

입력

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

출력

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

 

---

타일링 문제 2이다.

마찬가지로 dp로 해결할 수 있다.

N크기의 타일을 채우는 법은 한 개를 우선 둔 후 N-1 크기를 채우는 방법과

2개를 가로로 두고 N-2 채우기, 2x2 크기의 타일 하나를 두고 N-2를 채우는 방법으로 구성된다.

똑같이 점화식을 세워보면

dp[N] = dp[N-1] + dp[N-2] + dp[N-2]가 되므로 이 식에따라 문제를 풀면된다.

 

헷갈렸던 점은 두개를 세로로 세운 후 N-2를 채우는 방법까지 생각해야 하는건 아닌가 했지만, 이는 한 개를 세로로 세우는 방법과 겹치므로 예외로 둬야 했다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/2xn%20%ED%83%80%EC%9D%BC%EB%A7%81%202%20(11727%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
using namespace std;
int N;
int dp[1001];

int main()
{
	cin >> N;
	dp[0] = 0;
	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];
}