Study hard
(c++)백준 2133번: 타일 채우기 본문
https://www.acmicpc.net/problem/2133
☆가로 길이가 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;
}
'백준 > DP' 카테고리의 다른 글
(c++)백준 2225번: 합분해 (0) | 2020.06.10 |
---|---|
(c++)백준 9461번: 파도반 수열 (0) | 2020.06.10 |
(c++)백준 1699번: 제곱수의 합 (0) | 2020.06.09 |
(c++)백준 2579번: 계단 오르기 (0) | 2020.06.09 |
(c++)백준 1912번: 연속합 (0) | 2020.06.09 |