[C++] 백준(BAEKJOON) 11726

#include <stdio.h>
 
int n;
int cache[1001];
 
int dp (int x){
    if(x==1)
        return 1;
    
    if(x==2)
        return 2;
    
    if(cache[x] != 0) 
        return cache[x];
    
    return cache[x] = (dp(x-1) + dp(x-2)) % 10007;
}
 
int main(void){
    scanf("%d", &n);
    
    printf("%d", dp(n));
    
    return 0;
}