C :: 백준 2133번 - 타일 채우기

오늘은 계속 안풀리던 타일 채우기 문제를 풀었다. 문제는 아래와 같다.

위의 문제의경우 머리속에 떠오르는 대강의 알고리즘이 없어 바로 프로그래밍 하기에는 무리가 있었다. 계속 고민하다가 일정한 패턴을 찾았는데 그 패턴은 아래와 같다.

1. 홀수는 경우의수가 0이다.

2. f(2) = 3이다.

3. 매 모양마다 그 모양만이 가질 수 있는 경우의 수가 있다. 그것은 2가지이다.

4. f(n) = 3 * f(n-2)  +  2 * f(n-4)  +  2 * f(n-6) + 2 * f(n-8) + ... + 2 이다. 말로 조금 풀어쓰면 우선 홀수가 안되니 경우의 수를 체크하는것은 2단위로 체크를 하게 된다. 이때 발상이 중요한데 처음에는 2칸이 "늘어난다"라는 생각이 아니라 단순히크기가 커졌다고 생각을 하다보니  목표에 접근하지 못했다. 늘어난다고 생각을 해보면 늘어난 2칸에 들어갈 수 있는 경우는 f(2)일때와 같다. 그렇다면 그때의 경우의 수인 f(2) * f(n-2) 를 더해줘야하고, 이 늘어난  2칸에 4개짜리 모양이 들어갈 수 있는경우 2 * f(n-4) ... 이렇게 n에 가까워질때까지 더한 후에 마지막에 n일때만 가능한 경우의 수인 2를 더해주면 답을 구해낼 수 있다.

코드는 아래와 같다.

#include <stdio.h>

#include <stdlib.h>

int main(void)

{

int i,j,input,*p;

scanf("%d",&input);

if(input%2!=0){

printf("0");

return 0;

}

p = (int*)malloc(sizeof(int)*(input/2));

p[0]=3;

for(i=3;i<input;i+=2){

p[i/2]=3*p[(i-2)/2]+2;

for(j=1;j<i-2;j+=2){

p[i/2]+=2*p[j/2];

}

}

printf("%d",p[input/2-1]);

 

return 0;

}