/*
#include <stdio.h>
int rec(int n)
{
if(n==1)
return 1;
if(n>3)
return rec(n-3)+rec(n-2)+rec(n-1);
if(n==3)
return rec(n-2)+rec(n-1);
return rec(n-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n+1));
return 0;
}
#include <stdio.h>
int rec(int n,int i,int j)
{
printf("%d ",i);
if(i==n)
return 0;
if(i==j)
{
printf("\n");
i=1;
j++;
}
else
{
i++;
}
rec(n,i,j);
}
int main()
{
int n,i=1,j=1;
scanf("%d",&n);
rec(n,i,j);
return 0;
}
#include <stdio.h>
void cer(int i)
{
if(i==0)
return ;
printf("*");
cer(i-1);
}
void rec(int i,int n)
{
if(n==0)
return ;
cer(i);
printf("\n");
rec(i+1,n-1);
}
void main()
{
int i=1,n;
scanf("%d",&n);
rec(i,n);
return ;
}
재귀함수
memoization
#include <stdio.h>
int m[10000000]={};
int rec(int n)
{
if(n==0)
return 1;
if(m[n]!=0)
return m[n];
if(n==1)
return m[n]=rec(n-1)%1000;
if(n==2)
return m[n]=rec(n-1)%1000+rec(n-2)%1000;
else
return m[n]=rec(n-1)%1000+rec(n-2)%1000+rec(n-3)%1000;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n)%1000);
return 0;
}
#include <stdio.h>
long long int xy[501][501]={},r,c;
int one(int x,int y)
{
if(y>r)
return 0;
xy[x][y]=1;
if(x!=c)
one(x+1,y);
else
one(x=0,y+1);
}
int rec(int x,int y)
{
if(y>r)
return 0;
xy[x][y]=xy[x-1][y]%100000000+xy[x][y-1]%100000000;
if(x<=c)
rec(x+1,y);
else
rec(x=2,y+1);
}
int main()
{
int x=0,y=0;
scanf("%lld %lld",&r,&c);
one(x,y);
rec(x=2,y=2);
printf("%lld",xy[c][r]%100000000);
return 0;
}
*/
#include <stdio.h>
int main()
{
int k,n
scanf("%d",&c)
}