[백준] C++ 9095번 : 1, 2, 3 더하기

 

풀이과정

---

1. 재귀 함수를 사용한다.

 재귀함수의 인자인 값(currN)이 입력 받은 정수(N)와 같을 때까지 1,2,3만큼 증가시킨다.

인자의 값(currN)이 입력받은 정수 N과 같다면 횟수를 1 증가시켜 반환한다.

currN이 N보다 크다면 0을 반환한다.

 

2. dp를 사용한다.

 점화식은 f(1) = 1, f(2) = 2, f(3) = 4, 이후는 f(n) = f(n-1) + f(n-2) + f(n-3)이다.

코드

---

재귀

#include <iostream>
#include <string>
using namespace std;

int Func(int N,int currN, int iCount)
{
	
	if (N < currN) return 0;

	if (currN == N) return iCount+1;
	
	return Func(N, currN + 1, iCount) + Func(N, currN + 2, iCount) + Func(N, currN + 3, iCount);

}
 
int main()
{
	int N = 0, tc[12] = { 0, };
	cin >> N;

	for (int i = 0; i < N; ++i)
		cin >> tc[i];

	for (int i = 0; i < N; ++i)
		cout << Func(tc[i], 0, 0) << endl;


	return 0;
}

dp (Dynamic Programming)

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 12;

int main()
{
	int dp[MAX];
	int N = 0;
	cin >> N;

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	for (int i = 4; i < MAX; i++) {
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}

	for (int i = 0; i < N; ++i)
	{
		int n;
		cin >> n;
		cout << dp[n] << endl;
	}
	return 0;
}