백준 11727 : 2xn타일링 2 (Python)

본문 링크

N=int(input())

dp=[1,3]

for i in range(2,N):
    dp.append( (2*dp[i-2]+dp[i-1])%10007)
print(dp[N-1]%10007)

📌 어떻게 문제에 접근할 것인가?

혹시 2xn 타일링 1 문제를 풀지않았다면 먼저 풀고오기를 바란다.

2xn 타일링 1 본문 링크

n=5일때까지 시뮬레이션을 해보았을때

[1,3,5,11,21] 값이 나오는 것을 확인 할 수 있다.

일단 피보나치 값은 아니지만 증가하는 수열이다.
그렇다면 어떻게 증가할것인가?

2xn 타일링 1 문제에서는 2x1 , 1x2타일만을 사용했을때 피보나치 값을 사용했다.

그렇다면 2x2 타일이 추가된 시점에서 피보나치값에다가 어떤 특정한 값을 더한 패턴이지 않을까?
라고 접근해보았다.

따라서 $dp[i]= dp[i-1] + 2* dp[i-2]$ 라는 점화식이 만들어 진다.

5 라는 값은 3과 1x2의 합으로 , 11 은 5와 3x2의 합으로 나올 수 있다.

✅ 코드에서 주의해야할 부분

• $dp$ 를 10007로 나눈 값을 출력한다.