[백준_2133] 타일 채우기 python

dp 를 풀었을 때 뭔가 찜찜한 느낌이 들면

그 느낌은 결코 배신하지 않는 것 같다.

 

각 경우마다 새로운 조합이 2개씩 생겨난다는 것을 생각치 못하였다.

# dp 설계
dp = [
    0 for _ in range(31)
]

# dp 초기설정
dp[2] = 3
dp[4] = 11

# dp 채워넣기
for i in range(6, 31, 2):
    # 두번 전의 값 * 3
    dp[i] = dp[i-2] * 3

    # 네번째 전, 여섯 번째 전 ,,,
    for j in range(4, i, 2):
        # 각각 2개씩 경우의수가 붙음
        dp[i] += dp[i-j] * 2
    
    # 새로운 조합 2개 나옴
    dp[i] += 2

# n 입력
n = int(input())

# 출력
print(dp[n])