백준 2133 파이썬 python 타일 채우기 @@황소처럼 우직하게@@

n = int(input())

def sol(n):
    if n % 2 != 0:
        return 0
    else:
        dp = [0] * (n + 1)
        dp[0] = 1  # 0줄인 경우는 아무것도 안하는 경우 하나이니까
        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))

이런 타일 문제는요~

길이가 1칸일 때, 생길 수 있는 경우의 수.

길이가 2칸일 때, 길이 1칸 경우의 수와 겹치지 않으며 생길 수 있는 경우의 수.

길이가 3칸일 때, 길이 1~2칸 경우의 수와 겹치지 않으며 생길 수 있는 경우의 수.

길이가 4칸일 때, 길이 1~3칸 경우의 수와 겹치지 않으며 생길 수 있는 경우의 수.

...

해서 무한대까지 다 고려해줘야 됩니다.

근데 찾다보면 더 없다는 규칙이 보인다든지, 일정한 규칙이 보이겠죠? 

 

이번 타일 문제는요~

2칸일 때, 3가지 경우의 수

4칸일 때, 2가지 경우의 수

6칸일 때, 2가지 경우의 수

8칸일 때, 2가지 경우의 수

...

4부터 짝수칸일 때, 2가지 경우의 수라는 규칙을 보여줍니다.

그럼 식을 세워보면 

dp[n] = dp[n-2] * 3 + dp[n-4] * 2 + dp[n-6] * 2 + dp[n-8] * 2 + ... + dp[0] * 2

간단하죠? 구현하면됩니다.

이 때 dp[0] = 1 입니다. 아무것도없는건 아무것도 안한 경우 하나 있으니까요~ ㅋ