[백준] 2133번 타일 채우기

💡문제접근

• N이 홀수인 경우 2 X 1, 1 X 2 크기의 타일로 빈틈없이 채우는 경우는 불가능하다. 따라서 N이 홀수인 경우 나올 수 있는 모든 경우의 수는 0이 된다. 질문 게시판에 있는 테스트케이스와 내가 직접 계산한 경우의 수를 비교해서 문제를 해결했다.
• N의 입력값의 범위는 1 ≤ N ≤ 30으로 dp 배열을 선언할 떄 인덱스에러(IndexError)가 발생하지 않도록 주의하자.

💡코드(메모리 : 31256KB, 시간 : 40ms)

import sys
input = sys.stdin.readline

N = int(input())
dp = [0] * 31
dp[0] = 1	# dp[0] = 1 → 만들 수 없는 경우도 1가지로 취급
dp[2] = 3

# ex. 3 X 1 크기의 벽 : 0
# ex. 3 X 2 크기의 벽 : 3
# ex. 3 X 3 크기의 벽 : 0
# ex. 3 X 4 크기의 벽 : 11
# ex. 3 X 5 크기의 벽 : 0
# ex. 3 X 6 크기의 벽 : 41
# ex. 3 X 7 크기의 벽 : 0

if N < 4:
    if N == 0:
        print(1)
    elif N == 1 or N ==3:
        print(0)
    else:
        print(3)
else:
    for i in range(4, N+1):
        dp[i] = dp[i-2] * 4 - dp[i-4]
    print(dp[N])

💡소요시간 : 11m