[boj][c++] 9095 1,2,3더하기

9095 1, 2, 3 더하기

dp 카테고리에서 찾은 문제였는데 점화식은 찾았으나 입증할 방법이 없어서 조금 더 신빙성이 있는 dfs로 풀었다.
내가 찾은 점화식은 n이 4이상일 때 dp(n)=dp(n-1)+dp(n-2)+dp(n-3)이었는데 아마 dp 카테고리에 있으니 맞을거 같다.

dfs는 입력받은 n을 최대 버퍼로 생각하고 1, 2, 3을 n이 될 때까지 더해줬다. 반복문을 돌릴 때 주의한 부분은 1, 2, 3을 더했을 때 n을 넘는 경우가 있으므로 그 경우는 조건문을 걸어서 처리했다.

요즘 노트북 들고다니기가 귀찮아서 코드가 간단한 문제는 탭에서 모바일C로 풀고있다. vs의 편리함에서 멀어져서 오히려 좋은 것 같다. 코딩테스트 대비하는 느낌

#include <iostream>
using namespace std;

int N;
int cnt=0;

void dfs(int n)
{
	if(n==N)
	{
		cnt++;
		return;	
	}
	for(int i=1;i<=3;i++)
	{
		if(n+i<=N)
			dfs(n+i);	
	}	
}
		
int main()
{
	int number;
	cin>>number;
	for(int i=0;i<number;i++)
	{
		cin>>N;
		dfs(0);
		cout<<cnt<<"\n";
		cnt=0;
	}
	return 0;	
}