[백준] 알고리즘 2133. 타일 채우기
문제
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
입력
첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.
출력
첫째 줄에 경우의 수를 출력한다.
예제 입력 1
2
예제 출력 1
3
힌트
아래 그림은 3×12 벽을 타일로 채운 예시이다.
#include <stdio.h>
int arr[31];
int dp(int x) {
if (x == 0) return 1;
if (x == 1) return 0;
if (x == 2) return 3;
if (arr[x] != 0) return arr[x];
int result = 3 * dp(x - 2);
for (int i = 3; i <= x; i++) {
if (i % 2 == 0) {
result += 2 * dp(x - i);
}
}
return arr[x] = result;
}
int main() {
int x = 0;
scanf("%d", &x);
printf("%d\n", dp(x));
return 0;
}
점화식 : d[n] = 3 * d[n - 2] + 2 * d[n - 2x] ※ x > 1, (n - 2x) >= 0
'알고리즘 테스트 ⏲ > 백준' 카테고리의 다른 글
[백준] 알고리즘 2252. 줄 세우기 (0) | 2021.07.23 |
---|---|
[백준] 알고리즘 14852. 타일채우기 3 (0) | 2021.07.14 |
[백준] 알고리즘 11727. 2xn 타일링2 (0) | 2021.07.13 |
[백준] 알고리즘 11726. 2xn 타일링 (0) | 2021.07.13 |
[백준] 알고리즘 10989. 수 정렬하기 3 (0) | 2021.07.08 |