문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

www.acmicpc.net/problem/2133

  • 입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

  • 출력

첫째 줄에 경우의 수를 출력한다.

  • 힌트

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

예시

최종 코드

이전에 풀었던 2xn 타일링 문제랑 비슷한 문제라고 생각했는데 보기보다 어려웠다.

우선 n이 홀수인 경우는 타일을 알맞게 채울 수 없으므로 무조건 0이고, 짝수인 경우만 고려하면 된다.

  • n = 2 n=2

  • n = 4 n=4

  • n = 6 n=6

  • n n

n이 4일 때는 3*3

따라서 점화식은 dp[n] = dp[n-2]*3 + sum(dp[2:n-2:2])*2 + 2이다.

구현할 때에는 짝수만 저장하려고 dp 배열을 n개로 잡지 않고 n//2+1개로 잡았다.

n = int(input())
dp = [0]*(n//2+1)

if n%2 == 1:
    print(0)
else:
    dp[1] = 3
    for i in range(2, n//2+1):
        dp[i] = dp[i-1] * 3 + sum(dp[:i-1]) * 2 + 2
    print(dp[-1])

참고 사이트