C언어 백준 9095번 1, 2, 3 더하기

문제 풀이

귀납적으로 경우의 수를 나열하고, 나열된 숫자를 통해 점화식을 세웠습니다. 이 점화식을 메모이제이션을 통해 기록하였습니다.

 

하나씩 나열 해 본 결과

첫 번째 나열된 값 a[1] = 1;

두 번째 나열된 값 a[2] = 2;

세 번째 나열된 값 a[3] = 4;

네 번째 나열된 값 a[4] = 7;....

 

시험 때는 정확성을 위해 다섯 번째 나열된 값까지 구했을 것으로 보입니다.

결과적으로 a[n]=a[n-1]+a[n-2]+a[n-3] (n>=4) 점화식을 얻었습니다.

 

코드

#include <stdio.h>

int n;
int arr[1010]={0,};
	

int main(void)
{
	int T;
	scanf("%d",&T);
	for (int i=0; i<T; i++)
	{
		scanf("%d", &n);
		arr[0]=1;
		arr[1]=1;
		arr[2]=2;
		arr[3]=4;
		for (int i=4; i<n+1; i++)
		{
			arr[i]=((arr[i-1]+arr[i-2]+arr[i-3]));
		}
	
		printf("%d\n",arr[n]);
	}
}