[BOJ] 2133. 타일 채우기

Python3,DP

문제

입출력

입출력 예시

주요 포인트

n이 홀수일 때는 타일을 채울 수 없기 때문에 경우의 수가 0이다.

dp[n] 은
dp[n-2] * 3 + (dp[0] + dp[2] + .. + dp[n-4]) * 2 + 2(가로 길이 n일 때)로 나타낼 수 있다.

최종 코드

n = int(input())

dp = [0 for i in range(31)]

dp[2] = 3

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

피드백

기존 타일 문제보다는 더 까다로웠다. 경우의 수는 최대 3-4개까지만 하고 3xn으로 일반화를 시켜보도록 노력하자.

참고

https://jyeonnyang2.tistory.com/51