백준 알고리즘 2133 번, 다이나믹 프로그래밍 - 타일 채우기

https://www.acmicpc.net/problem/2133

<문제>

3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구해보자

<입력>

첫째 줄에 N(1<=N<=30)이 주어진다. ( ex > 2 ) 

<출력>

첫째 줄에 경우의 수를 출력한다. ( ex> 3 )

<힌트>

아래 그림은 3x12 벽을 타일로 채운 예시이다.

 3×N을 1×2, 2×1로 채우는 방법의 수를 거꾸로 생각해, D[i][j] = 3×i를 채우는 방법의 수, i열의 상태는 j 이렇게 바꾸어 생각해 보자

그러면, 

 < 풀이 >