[프로그래머스] 3 x n 타일링 / 파이썬

programmers.co.kr/learn/courses/30/lessons/12902#

코딩테스트 연습 - 3 x n 타일링

처음에는 너무 쉽게 생각했다.
처음 생각한 점화식은 dp[i] = dp[i-2] * 3 + dp[i-4] * 2 였다.
하지만 오답이 난 순간 무언가를 빼먹었나 라는 생각을 하게되었고, 나름 쉽게 규칙을 찾을 수 있었다.

우선 n이 홀수인 경우를 생각해보자

3 x 홀수 => 홀수 이다.
즉 홀수인 경우는 홀수가 나오므로, 길이가 2인 타일들로는 채우는 것이 불가능함이 자명하다.

짝수인 경우를 생각해보자.
짝수를 n이라고 가정해보자.
우선 2개로 만들 수 있는건 그려보면 3개가 나온다.
그러니 n-2개로 만들 수 있는 수 * 3으로 만들 수 있다.

그리고 이게 그려보면 재밌는게 나오는데
길이가 4인 타일로 만들 수 있는 이상한 모양이 두 개 나온다.
길이가 6인 타일로 만들 수 있는 이상한 모양이 두 개 나온다.
길이가 8인 ..
길이가 2*k인 타일로 만들 수 있는 이상한 모양이 두 개 나온다.

이제 규칙을 찾았다.

dp[i] = dp[i-2] * 3 + for n in range(2, i+1, 2) { dp[i-n] * 2 } 임이 확실함을 알 수 있다.

def solution(n):
    MOD = 1000000007
    answer = 0
    if n % 2 == 1:
        return 0
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp[2] = 3
    for i in range(4, n+1, 2):
        dp[i] = (dp[i-2] * 3)
        for j in range(4, i+1, 2):
            dp[i] += (dp[i-j] * 2)
        dp[i] %= MOD
    return dp[n]