#11726

#11726

문제

풀이

N=int(input())

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

print(dp[N]%10007)

사실 피보나치와 코드는 똑같다. 이 문제를 보고 캐치할 수 있는 아이디어는 바로 N번째의 블록 수는 N-2번째의 블록 수와 N-1번째의 블록수의 합으로 이루어진다는 것이다.
n-1 에선 1×2를 추가해주면 되니 dp[n-1] * 1
n-2 에선 2×1를 추가해주면 되니 dp[n-2] * 1
결국 dp[i]=dp[i-1]+dp[i-2]와 같은 피보나치 수열이 나오게 되는 것이다.