/*
#include<stdio.h>
void rec(int b)
{
if(b==0) return 0;
rec(b-1);
printf("%d\n",b);
}
int main()
{
int a,b;
scanf("%d",&b);
rec(b);
return 0;
}
*/
/*
#include<stdio.h>
int rec(int n)
{
if(n==1)
{
return 0+1;
}
if(n%2==0)
{
return rec(n/2)+1;
}
else if(n%2==1)
{
return rec(n*3+1)+1;
}
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n));
return 0;
}
#include<stdio.h>
int a[500]={};
int rec(int n)
{
if(n==0) return 0;
if(n%10==0)
{
rec(n/10);
}
else
{
a[n] = n+rec(n/10);
return a[n]);
}
}
int main()
{
int n;
scanf("%d",&n);
if(n==0)
{
printf("0");
return 0;
}
printf(rec(n));
return 0;
}
*/
/**
메모이제이션 memoization
-> 계산했던거를 메모해놓고 나중에 다시계산안하고 바로 사용하기
1. 저장할 배열 만들기 (0으로 초기화)
2. f(n) 실행할때, 맨 처음에 일단 a[n]이 0이 아닌수라면 그거 바로 리턴하기
0이라면 원래대로 계산하고, 배열에 저장하기
*/
/*
#include<stdio.h>
int a[201]={};
int rec(int n)
{
if(n==1 || n==2)
{
return 1;
}
if(a[n]==0)
{
a[n]=rec(n-2)+rec(n-1);
}
return a[n]%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n));
return 0;
}
*/