[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 타일 채우기 (2133)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 타일 채우기 (2133)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 타일 채우기 (2133)

 

---

 

2133번: 타일 채우기

[ 문제 ]

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

[ 입력 ]

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

[ 출력 ]

첫째 줄에 경우의 수를 출력한다.

 

---

[ 코드 ]

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

int dp[31]; // 3*N 크기의 벽을, 2*1 1*2 크기의 타일로 채우는 경우의 수
// 마지막에 나올 수 있는 경우의 수를 생각해보고, 1부터 하나씩 그려보기

int main() {
	int N; // 3*N 크기의 벽
	cin >> N;

	dp[0] = 1;

	for (int i = 2; i <= N; i+=2)
	{
		dp[i] = (3 * dp[i - 2]); // 기본 3*3으로 마지막에 올 수 있는 경우의 수

		for (int k = 4; k <= i; k+=2)
		{
			dp[i] += (2 * dp[i - k]); // 3*2i으로 마지막에 올 수 있는 다른 경우의 수들
            // ex. i=8, dp[4]*2 = 경우의 수 2*2
			// k+=2를 하는 이유는, ex. i=6인 경우에도, dp[2]의 경우의 수 3가지 + 4로 만드는 경우의 수인 2가지가 합쳐질 수 있기 때문
            // i=10인경우도 마찬가지. dp[6] 인경우 + 4로 만드는 경우의 수인 2가지 합쳐질 수 있음. dp[2] + 4로 만드는 경우의 수 2가지 + 4로 만드는 경우의 수 2가지 가능
		}
	}
	
	cout << dp[N] << '\n';
	return 0;
}