[백준] 2133 '타일 채우기' 파이썬(python)

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

n = int(input())

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

Point

• 타일문제로서 규칙을 먼저 찾아보면 홀수는 성립되지 않고 짝수만 성립된다는 것을 우선 알 수 있다.
• 그리고 n=2일 때는 3이지만, 그 이후 짝수인 4, 6, 8 ...에서는 이전 규칙과 상이한 패턴이 단지 2가지만 추가된다는 것을 알 수 있다.(밑의 그림처럼 중간에 두개가 들어간 형식이다. 이것을 반대로 한 것까지 해서 총 2가지의 새로운 패턴이 추가된다. 6, 8, 10 ... 짝수에서는 계속해서 이런 모양이 나온다)

• 따라서 dp[n] = dp[n-2] * 3 + dp[n-4] *2 + ... dp[0] * 2 라는 식을 세울 수 있다.
• 이전의 결과값을 사용하는 것이기에 dp테이블을 이용한 DP문제라고 할 수 있고, 해당 규칙을 코드로 나타내면 위와 같다.