Algorithm/백준
[백준][2133번] 타일 채우기
1일1코딩
2020. 3. 26. 22:29
https://www.acmicpc.net/problem/2133
2133번: 타일 채우기
문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다....
www.acmicpc.net
풀이과정
그림이 필요하므로 일단 생략..
소스코드
더보기
#include <stdio.h>
#include <string.h>
int dp[31];
int N;
int solution(int n)
{
if (dp[n] != -1) { return dp[n]; }
dp[n] = 0;
if (n % 2 == 1) {
return dp[n];
}
if (n - 2 >= 0) {
dp[n] = solution(n - 2) * 3;
}
if (n - 4 >= 0) {
for (int i = 4; i <= n; i+=2) {
if (i % 2 == 0) {
dp[n] += solution(n - i) * 2;
}
}
}
return dp[n];
}
int main()
{
scanf("%d", &N);
memset(dp, -1, sizeof(dp));
dp[0] = 1;
dp[1] = 0;
dp[2] = 3;
dp[3] = 0;
printf("%d\n", solution(N));
}