나의 풀이
# 입력
import sys
read = sys.stdin.readline
arr = [1, 2, 3] + [0]*1000
# 처리
for i in range(n:=int(read().strip())):
arr[i+2] = (arr[i+1] + arr[i]) % 10007
print(arr[n-1])
CODE REVIEW
(1*2)한 개 또는(2*1)위아래로 두 개 쌓는 방식을 택할 수 있어서,n을 1, 2의 합으로 나타내는 경우의 수를 구하는 문제로 바뀐다.- 점화식은 $a_{n+2} = a_{n+1} + a_{n}$ n+1에
(1*2)한 개 넣거나, n에(2*1)위아래로 두 개 넣는 경우의 합으로 계산할 수 있다. - cf) 피보나치 수열과 동일.