591 : 함수3 - 자가진단5

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=228&sca=10d0

JUNGOL | 함수3 - 자가진단5 > 문제은행

#include<bits/stdc++.h>
int f(int p)
{
	if(p==1)return 1;
	return f(p/2)+f(p-1);
}
int main()
{
	int i,k,n;
	scanf("%d",&n);
	k=f(n);
	printf("%d\n",k);
	return 0;
}

위 코드는 입력 값 n이 커지면, 상당히 느려진다.

그래서 아래와 같이 메모이제이션을 적용하였다.

 

#include<bits/stdc++.h>
int c[1004]={0,};
int f(int p)
{
	if(p==1){
		return 1;
	}
	else if(c[p]!=0){
		return c[p];
	}
	else{
		c[p]=f(p/2)+f(p-1);
	    return c[p];
	}
}
int main()
{
	int i,k,n;
	scanf("%d",&n);
	k=f(n);
	printf("%d\n",k);
	return 0;
}