/*#include<stdio.h>
void f(int n)
{
if(n==1)
{
printf("1");
return;
}
if(n==0)
return;
f(n/2);
printf("%d", n%2);
}
int main()
{
int n;
scanf("%d", &n);
if(n==0)
{
printf("0");
return ;
}
f(n);
}*/
/*
#include<stdio.h>
void f(int i, int j, int l)
{
if(i==j&&j==l)
{
printf("*");
return;
}
else if(i==j)
{
printf("*\n");
f(i=1,j+1,l);
}
else
{
printf("*");
f(i+1,j,l);
}
}
int main()
{
int n;
scanf("%d", &n);
f(1, 1, n);
}
f(n)
n=1 1
n=2 1
n=3 ~ f(n) : f(n-1) + f(n-2)
memoization : 계산한 적 있는 값을 다시 계산하지 않기 위해서
int memo[50]={};
memo[x]==0 (계산한적없는)
memo[x]!=0 (계산한적이있는)
#include <stdio.h>
int memo[201]={};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if(n<=2) return memo[n]=1;
return memo[n]=f(n-1)+f(n-2);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d",f(n));
}
*/
/*
#include<stdio.h>
int m[100001]={};
int f(int n)
{
if(m[n]!=0)return m[n];
if(n==1)return m[n]=1;
if(n==2)return m[n]=2;
if(n==3)return m[n]=4;
return m[n]=(f(n-1)+f(n-2)+f(n-3))%1000;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n));
}
#include<stdio.h>
int m[51][51]={};
int f(int r, int c)
{
if(m[r][c]!=0)return m[r][c];
if(r==1||c==1)return m[r][c]=1;
if(r==2&&c==2)return m[r][c]=2;
m[1][c]=1;
m[r][1]=1;
return m[r][c]=(f(r-1, c)+f(r, c-1))%100000000;
}
int main()
{
int r, c;
scanf("%d %d", &r, &c);
printf("%d", f(r, c));
}
#include<stdio.h>
int m[15][15]={};
int f(int k, int n)
{
if(m[k][n]!=0)return m[k][n];
if(k==0||n==0) return m[k][n]=n;
return m[k][n]=f(k,n-1)+f(k-1,n);
}
int main()
{
int k, n;
while( scanf("%d %d", &k, &n) != EOF )
printf("%d\n", f(k, n));
}
c언어 문법
-> c언어 자료구조 or JAVA... or ...
*/