<Baekjoon>#2133 3n 타일 채우기 (3n Tiling) c
처음 타일링 문제를 접했을 때는 이게 도대체 뭐지? 하는 생각이 들었다. 동적 프로그래밍을 처음 접한 문제가 타일링 이었기 때문에 더욱 더 낯설고 이상(?)했다.
이 문제를 풀기 전에 #11726, #11727 2n 타일링을 먼저 공부해야 이해가 더 잘 된다. 타일링만으로도 엄청 많은 문제를 응용해서 낼 수 있을 것 같다.
타일링 문제의 경우 끝을 기준으로 나눠서 생각해야 한다.
3 x k 인 타일의 경우 3 x (k-2), 3 x 2
먼저 n=1 인 경우부터 본다
그림을 굳이 그리지 않고 생각해도 n이 홀수인 경우에는 만들 수 없다는 것을 알 수 있다.
n=2인 경우 3가지가 나온다
보통 타일링 문제의 경우 n이 2,3 인 경우까지 해보면 점화식이 나오는데 이 경우에는 4까지 해봐야한다.
n이 4인 경우를 보면 n=2일 때로 쪼갤 수 없는 모양이 2개 존재한다
n이 6일 때도 쪼갤 수 없는 모양이 2개 존재한다.f[4]=3 x f[2] + 2 x f[0] = 11
n이 4,6,8,10... 등등 증가할 때마다 각각 쪼갤 수 없는 모양이 2개씩 존재한다.
따라서
f[n]=3 x f[n-2]+2 x f[n-4]+2 x f[n-6]+...+2 x f[0]
와 같은 점화식이 나온다.
(학교 다닐 때 교수님께서 만들어진 코드만 보면 쉽게 점화식을 도출하는 것 처럼 보이지만 정말 치열하게 생각하고 파고들어야 알 수 있는 거라고 했다..ㅠㅠ 진짜 어렵다)
#include<stdio.h>
int f[31];
int dp(int n) {
if (n == 0) return 1;
if (n == 1) return 0;
if (n == 2) return 3;
if (f[n]) return f[n];
else {
f[n] = 3 * dp(n - 2);
for (int i = 4; i <= n; i += 2)
f[n] += 2 * dp(n - i);
}
return f[n];
}
int main() {
int n;
scanf_s("%d", &n, 1);
printf("%d", dp(n));
return 0;
}
Author And Source
이 문제에 관하여(<Baekjoon>#2133 3n 타일 채우기 (3n Tiling) c), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon2133-3n-타일-채우기-3n-Tiling-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)