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

문제

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

---

문제 요약

2 × n 직사각형을 1 × 2, 2 × 1, 2 × 2 타일로 채우는 방법의 수를 출력한다.  

---

코드

#include <iostream>

#define MAX_N 1000

using namespace std;

int n;

int dp[MAX_N + 1]; 
// dp[i]: 크기 i까지 타일로 채우는 방법의 수

int main() {
	cin >> n;

	dp[1] = 1;
	dp[2] = 3;

	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 2]) % 10007;
	}

	cout << dp[n];

	return 0;
}

---

코드 설명

Bottom - Up 방식의 다이나믹 프로그래밍을 통해 문제를 해결한다.

 

메모이제이션 테이블 dp를 정의한다.

 

dp[i]

 

= 2 × i 직사각형을 1 × 2, 2 × 1, 2 × 2 타일로 채우는 방법의 수

 

= 2 × (i - 1) 직사각형을 1 × 2, 2 × 1, 2 × 2 타일로 채우고, 오른쪽에 2 × 1 타일을 놓는 방법

 

+ 2 × (i - 2) 직사각형을 1 × 2, 2 × 1, 2 × 2 타일로 채우고, 오른쪽에 1 × 2 타일 두 개를 놓는 방법

 

+ 2 × (i - 2) 직사각형을 1 × 2, 2 × 1, 2 × 2 타일로 채우고, 오른쪽에 2 × 2 타일을 놓는 방법

 

=> dp[i - 1] + dp[i - 2] + dp[i - 2]

---

고찰

 2 × n 타일링 문제에 추가로, 2 × 2 타일이 놓이는 경우의 수를 생각하여 풀면 된다.

 

https://daily-program-ing.tistory.com/119

[백준/Python] 2×n 타일링