[백준] 11727번 2xn 타일링 2

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

 

 

이 문제에서는 이런 식으로 타일 그림을 그려봤는데, 솔직히 규칙성을 찾기는 어려웠다 ㅠ

 

그런데 이렇게 마구잡이로 찾지 말고

그 직전에 했던 것에 박스를 추가하는 방식을 사용하는 것이다.

그래서 발견한 규칙성은 dp[i] = 2*i 길이 직사각형 만드는 방법 수 = dp[i-1] + dp[i-2]*2

 

N = int(input())
# dp 배열 초기화
dp = [0]*(N+1)
dp[1], dp[2] = 1,3

for i in range(3,N+1) : 
    dp[i] = dp[i-1] + dp[i-2]*2

ans = dp[N]
print(ans%10007)