11726

import sys
input = sys.stdin.readline

n = int(input())

def dpsum(t):
    if t == 1:
        return 1
    elif t == 2:
        return 2
    else:
        return dpsum(t-1)+dpsum(t-2)

result = dpsum(n)%10007

print(result)

시간초과 뜸..

 

import sys
input = sys.stdin.readline

n = int(input())

value = [0]*1001
value[1] = 1
value[2] = 2

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

result = value[n] % 10007

print(result)

9095번과의 차이점은 숫자 범위가 크기 때문에 메모리를 사용하더라도 값을 미리 구해 저장해 두는 것이 오히려 시간은 적게 걸렸다는 점 같다.

 

#동적계획법