[백준][Python] 11727번 2×n 타일링 2

11727번: 2×n 타일링 2

 

코드

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

 

설명

규칙을 찾기가 되게 어려웠다.. 일단 그 전에 푼 2×n 타일링과 달리 2×2 타일이 추가되었기 때문에 n이 짝수일 때와 홀수일 때의 규칙이 따로따로 존재하겠다는 생각이 들었다. 그래서 n이 5일 때까지 값을 구해보니 

n = 1 -> 1
n = 2 -> 3
n = 3 -> 5
n = 4 -> 11
n = 5 -> 21

이렇게 나왔다. 이걸 보고

n이 홀수일 때 dp[i] = (dp[i-2] * 4) + 1

n이 짝수일 때 dp[i] = (dp[i-2] * 4) - 1

임을 알아냈다.