#include<cstdio>
#include<algorithm>
int fibo[10000][300]={0};
const int MAX=1000000000;
int main(void)
{
fibo[1][0]=1;
fibo[2][0]=1;
int input;
scanf("%d",&input);
for(int i=3;i<=input;i++)
{
for(int j=0;j<299;j++)
{
fibo[i][j]+=fibo[i-1][j]+fibo[i-2][j];
if(fibo[i][j]>=MAX)
{
fibo[i][j+1]+=fibo[i][j]/MAX;
fibo[i][j]%=MAX;
}
}
}
bool first_not_zero_find=false;
for(int i=299;i>=0;i--)
{
if(!first_not_zero_find)
{
while(fibo[input][i]==0)
i--;
first_not_zero_find=true;
printf("%d",fibo[input][i]);
continue;
}
printf("%9d",fibo[input][i]);
}
}
머가 틀린건가요? ㅜㅜ
