[BOJ/백준 11727][C++] 2xn 타일링 2

문제

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

 

문제 내용

2 * n 크기의 직사각형을 1 * 2, 2 * 1, 2*2 타일로 채우는 가지 수를 구하는 문제이다.

2*n 타일링 문제에서 2*2 타일이 하나 늘어난 경우이다.
https://gyong0117.tistory.com/73

[BOJ/백준 11726][C++] 2xn 타일링

 

문제 풀이

2*n 타일링 문제와 같이 dynamic programming 문제이다.
규칙 또한 2*n 타일링 문제와 같다.

규칙을 찾기 위해 나열을 해 보겠다.

dp[1] = 1;  // I

dp[2] = 3; // II, =, ㅁ

dp[3] = 5;  // III,I=,=I,Iㅁ,ㅁI

dp[2] 왼쪽에 I 추가  III, I=,Iㅁ
dp[1] 왼쪽에 = 추가  =I
dp[1] 왼쪽에 ㅁ추가  ㅁI

dp[4] = 11; 

dp[3] 왼쪽에 I추가   IIII,II=,I=I,IIㅁ,IㅁI
dp[2] 왼쪽에 =추가   =II,==, =ㅁ
dp[2] 왼쪽에 ㅁ추가  ㅁII,ㅁ=,ㅁㅁ

 

문제의 규칙을 정리해보면, dp[n] = dp[n-1] + 2 * dp[n-2] 가 나온다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int dp[1005];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n; cin >> n;
	dp[1] = 1;  // I
	dp[2] = 3;	// II, =, ㅁ
	dp[3] = 5;  // III,I=,=I,Iㅁ,ㅁI
	//dp[2] 왼쪽에 I 추가  III, I=,Iㅁ
	//dp[1] 왼쪽에 = 추가  =I
	//dp[1] 왼쪽에 ㅁ추가  ㅁI

	//dp[4]의 경우 11이다. (n-1)+2(n-2)
	//dp[3]왼쪽에 I추가   IIII,II=,I=I,IIㅁ,IㅁI
	//dp[2]왼쪽에 =추가   =II,==, =ㅁ
	//dp[2]왼쪽에 ㅁ추가  ㅁII,ㅁ=,ㅁㅁ


	//문제 해결
	for (int i = 4; i <= n; i++) {
		dp[i] = (dp[i - 1] + 2*dp[i - 2]) % 10007;
	}

	//결과 출력
	cout << dp[n] << '\n';
}

 

문제 코드 설명

1) 문제 해결

반복문을 통해 dp[n]의 값을 구하면 된다.
이때 출력 조건이 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 이므로 dp[n-1]+2*dp[n-2]를 10007로 나눈 나머지를 dp[n]에 넣으면 된다.