[백준 9095] 1, 2, 3 더하기

풀이법

숫자 N은 N-1 에서 +1 되서 만들어질 수 있고,

N-2에서 +2를 해서 만들어 질 수도 있고,

N-3에서 +3을 해서 만들어 질 수 있다.

 

이를 정리하면, 

 

DP[N] : 숫자 N이 표현될 수 있는 방법의 수

 

DP[N] = DP[N-1] + DP[N-2] + DP[N-3]

 

예를 들어,

 

10이 표현될 수 있는 방법의 수는

= 9( 10 - 1 )가 표현될 수 있는 방법의 수

+ 8( 10 - 2 )이 표현될 수 있는 방법의 수

+ 7( 10 - 3 )이 표현될 수 있는 방법의 수

 

#include <iostream>
#define MAX		11
using namespace std;

int T;
int dp[MAX];

int go(int n)
{
	if (n == 0)
		return 1;
	else if (n < 0)
		return 0;

	int& ret = dp[n];
	if (ret != 0) return ret;

	return ret = go(n - 1) + go(n - 2) + go(n - 3);
}

int main()
{
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;

		cout << go(n) << endl;
	}
	return 0;
}