/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include<stdio.h>
void f(int n) {
if(n==0) {
return;
}
f(n-1);
printf("%d\n", n);
}
int main() {
int n;
scanf("%d", &n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0)
{
return;
}
printf("%d\n",n);
f(n-1);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
a부터 b까지의 자연수 출력하기
*/
/*
#include <stdio.h>
void f(int a, int b)
{
if(a>b)
{
return;
}
if(a%2==1)
{
printf("%d ",a);
}
f(a+1,b);
}
int main()
{
int a,b;
scanf("%d %d",&a,&b);
f(a,b);
return 0;
}
f(a) : return (1~ a합)
return (1~a-1합)+a
return f(a-1)+a;
#include <stdio.h>
int f(int a)
{
if(a==1) return 1;
else return f(a-1)+a;
}
int main()
{
int a;
scanf("%d",&a);
printf("%d",f(a));
return 0;
}
/*
1912 1915 (return o)
1928 (void - printf)
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1) return 1;
else return f(n-1)*n;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
f(n) : n번째 피보나치수
f(1) return 1;
f(2) return 1;
f(3) return f(2)+f(1);
f(4) return f(3)+f(2);
....
f(n) return f(n-1)+f(n-2); (n이 3이상이때만)
첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다
// memoization memo[n] = 계산한 적이 있는 f(n)을 저장
#include <stdio.h>
int memo[201]={};
int f(int n)
{
//계산한 적이 있을 때
if(memo[n]!=0) return memo[n];
//계산한 적이 없을 때
if(n<=2) return memo[n]=1;
else return memo[n] = (f(n-1)+f(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
void : 1928 1929 1953 1920
return 값 잆고 memoization : 1916 3702 3704 1930
*/
/*
#include <stdio.h>
int arr[51][51]={};
int f(int a,int b)
{
if(arr[a][b]!=0)
{
return arr[a][b];
}
if(a==1||b==1)
{
return 1;
}
else
{
return arr[a][b]= (f(a-1,b)+f(a,b-1))%100000000;
}
}
int main()
{
int a,b;
scanf("%d %d",&a,&b);
printf("%d",f(a,b));
return 0;
}
*/