11727. [Python]2*n 타일링 2

1. 문제

 

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

11727번: 2×n 타일링 2

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• DP(Dynamic Programming)

 

3. 파이썬 코드

 

# 1 1
# 2 3
# 3 5
# 4 11
# 5 21
# 6 43
# 7 85
# 8 171

N = int(input())
# DP 설정
DP = [1, 3]

for i in range(2,N):
    # 이전 값 + 이전 전 값 * 2 하면 다음 값
    DP.append((DP[i-1] + DP[i-2]*2)%10007)
print(DP[N-1])

 

4. 문제를 풀고난 후 생각

 

• 규칙을 찾고 점화식을 찾는 문제는 5개정도 그려보고 규칙을 찾는 것이 문제를 푸는데 도움이 된다.

• 이전 값 + 이 전전 값*2 한 값이 다음 값으로 나오는 것을 확인할 수 있다.

 

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(Dynamic Programming)