백준 11727 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

기존에 풀었던 2 x n 타일링 1에서 2x2 도형이 하나 추가되었다.

 

처음에 완전히 잘못 접근했다.

 

그래서 이번 문제를 푸는 데에는 오랜 시간이 걸렸고, 다른 블로그의 글을 참고했다.

 

여러 블로그를 돌아도 풀이에 이해가 되지 않았는데, 단 한 블로그만이 나를 이해시켰다.

 

굉장히 잘하시는 분 같다.

 

혹시 나와 같은 분들이라면 아래 링크를 통해 직접 방문해 보길 추천한다.

https://changsroad.tistory.com/104

[Python] 백준 #11727- 2xn타일링 2

 

요약하면, 점화식은 n[i] = n [i-1] + (n [i-2] x 2) 이 도출된다.

 

해당 점화식을 풀어 설명해 보겠다.

 

n [i] = n [i-1]의 도형에 1 x 2 도형이 우측에 붙는다 + n [i-2]의 도형에 = 도형과 ㅁ 도형이 우측에 붙는다 

부디 이 종이 한 장이 설명이 되었기를 바라며.

 

코드

 

import sys

input = sys.stdin.readline

n = int(input())

dp = [1,3,5] * 334

for i in range(2, n+1):

    dp[i] = dp[i-1] + 2 * dp[i-2]

print(dp[n-1]%10007)