#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]와 같은 피보나치 수열이 나오게 되는 것이다.
Author And Source
이 문제에 관하여(#11726), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cherriverhee/11726저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)