[python] 11726. 2*n 타일링

 

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

 

풀이 

 

계속해서 dp문제를 풀고 있습니다. 

앞서 다른 게시글에서도 말씀드렸듯이, dp는 점화식을 구하는게 문제 해결의 핵심입니다 !

 

아래의 그림처럼 n이 1일 때부터

차근차근 경우의 수를 생각해보시면 점화식을 구할 수 있습니다.

 

아, 저는 dp를 (n+1)만큼만 구해서 답을 출력하려고 했으나 index error가 나오더라구요. 

n이 1이거나 2일 때, error가 발생하기 때문입니다.

 

따라서 dp는 문제와 같이 1000까지 구해야 오류 없이 정답을 도출할 수 있습니다.

 

 

 

 

n = int(input())
dp = [0 for _ in range(10000)] # (n+1)만큼 하면 index error

dp[1] = 1
dp[2] = 2

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

print(dp[n] % 10007)