Data Structure&Algorithm/Dynamic Programming

타일 채우기 - [백준 2133번]

타일 채우기 - 백준 2133번 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 풀이 dp[1] n = 3 일 때, 경우의 수 : 3 dp[1] = 3 dp[2] n = 4 일 때, 경우의 수 : 11 dp[1] * dp[1] + 2 ( 새로운 모양 2개 ) dp[3] n = 6 일 때, 경우의 수 : 41 dp[1] * dp[2] + dp[2] * 2 ( dp[2] * 새로운 모양 ) + 2 ( 새로운 모양 2개 ) dp[4] n = 8 일 때, 경우의 수 : 153 dp[1] * dp[2] + dp[3] * 2 ( dp[2] * 새로운 모양[2] 2개 ) + dp[2] *..