백준/DP
(c++)백준 2133번: 타일 채우기
Nimgnoej
2020. 6. 10. 15:07
https://www.acmicpc.net/problem/2133
2133번: 타일 채우기
문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복��
www.acmicpc.net
☆가로 길이가 2 늘어날 때마다 케이스가 2개씩 더 늘어난다.
※점화식※
dp[0] = 1 (추가 케이스 더할 때 필요)
dp[1] = 0
dp[2] = 3
dp[x] = 3 * dp[x-2] + 2 * dp[x-4] + ··· + 2 * dp[0] (마지막 항은 추가케이스 2개 더하는 항)
#include <iostream>
using namespace std;
int N;
long long dp[31];
void DP() {
dp[0] = 1;//추가 케이스 더할 때 필요
dp[1] = 0;
dp[2] = 3;
//N이 짝수일 때만 타일을 채울 수 있음
for (int i = 4; i <= N; i += 2) {
for (int j = 2; j <= i; j += 2) {
int Mul = j == 2 ? 3 : 2;//추가 케이스 개수
dp[i] += Mul * dp[i - j];
}
}
cout << dp[N] << endl;
}
int main() {
cin >> N;
DP();
return 0;
}