[baekjoon] 백준 11727번 : 2*n 타일링 2 (by python 파이썬) 다이나믹 프로그래밍

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

11727번: 2×n 타일링 2

 

정답 code

# 2*n 타일링 2
import sys
input = sys.stdin.readline

n = int(input())
cnt = [1,3]
for i in range(2,n+1):
    cnt.append( cnt[i-1] + cnt[i-2]*2)
    
print(cnt[-2]% 10007)

 

solution

전에 11726번 2*n타일링에서 유사한 문제를 풀었을때 규칙을 이용해 풀었던 기억이 있어 이 문제 역시 규칙을 찾아보았다.

 

1 -> 1

2 -> 3

3 -> 5

4 -> 11

5 -> 21

.

.

.

규칙 n = (n-i) + (n-i)*2

이런식으로 나열 되는데 처음에는 규칙을 찾기 정말 힘들었다. 

 

아래 블로그의 해당 규칙을 체계적으로 찾는 과정이 나와있다.

https://cijbest.tistory.com/21

[백준 11727 : PYTHON] 2xn 타일링 2