11726: 2xn 타일링

문제

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

• % 10007을 해주지 않아 오답을 받았다.
• dp = [0] * (n+1)에서 IndexError를 받았는데, n == 1일 때 dp[2]가 Index 범위를 초과하기 때문이다.

풀이

n = int(input())
dp = [0] * 1001
dp[1], dp[2] = 1, 2

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

print(dp[n] % 10007)

• dp[1] = 1 ( | )
• dp[2] = 2 ( ||, = )
• dp[3] = 3 ( |||, =| / |= )
  -> 즉 dp[2]에 |를 붙인 것 + dp[1]에 =를 붙인 것
• dp[4] = 5 ( ||||, =||, |=| / ||=, == )
  -> 즉 dp[3]에 |를 붙인 것 + dp[2]에 =를 붙인 것
  ...

따라서 dp[k] = dp[k-2] + dp[k-1]이다.