XMU1428 귀속 횟수 멋짐

1428.Hofstadter G-sequence
Time Limit: 1000 MS        
Memory Limit: 65536 K
Total Submissions: 228 (66 users)        
Accepted: 42 (39 users)
[ My Solution ]
Description
Hofstadter G-sequence는 재미있는 수열이지만, 이 편폭에 한계가 있기 때문에 우리는 구체적인 소개를 하지 않는다.다음 코드는 구하는 함수 G(n)가 Hofstadter G-sequence 수열입니다. int G(int n) {if(n <=1)return 1;return n n - G(G(n -1);}물론 이 문제의 요구는 함수 G(n)의 값을 구하는 것이 아니라 정수 x를 정하는 것입니다. 이 함수를 사용하여 G(x)의 값을 계산하려면 함수 G(n)를 몇 번 호출해야 합니까?
Input
입력은 한 줄, 정수 x (1 <= x <= 1000000) 하나입니다.
Output
답안이 매우 클 수 있기 때문에, 당신은 1000000007의 모형을 취한 후의 결과를 출력하기만 하면 됩니다.
Sample Input
삼
Sample Output
오
Source
http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1428
코드 자세히 보기

#include <stdio.h> 
#include<string.h> 
int f[1000011],ans[1000011];  
const  int  mod=1000000007;  
void get()
{
	int i,j;
	    f[1]=1;
    for(i=2;i<=1000000;i++)  
    {  
        f[i]=i-f[f[i-1]];  
    }  
    ans[1]=1;  
    for(i=2;i<=1000000;i++)  
    {  
        ans[i]=(ans[i-1]%mod+ans[f[i-1]]%mod+1)%mod;  
    }  
}
int main()  
{
    int i,j,m,n;  
    get();
    while(scanf("%d",&n)==1)  
    { 
        printf("%d
",ans[n]);  
    }  

    return 0;  
}