백준 알고리즘 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 이렇게 바꾸어 생각해 보자
그러면,
< 풀이 >