[백준/BOJ] 백준 9095번 : 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

정수 n을 1,2,3의 합으로 나타내는 방법은, n에서 1을 선택하고 n-1에 대해 1,2,3의 합으로 나타내는 방법과 n에서 2을 선택하고 n-2에 대해 1,2,3의 합으로 나타내는 방법과 n에서 3을 선택하고 n-3에 대해 1,2,3의 합으로 나타내는 방법을합친것이다.

 

코드

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

int cache[12];

//n을 1,2,3의 합으로 나타내는 방법의 수
int solve(int n)
{
	int& ret = cache[n];

	//ret가 -1이 아니라면 이미 계산한적이 있는 값이다
	if (ret != -1)
		return ret;

	//기저사례
	if (n == 1) //n이 1일때 1,2,3의 합으로 나타내는 방법의 수 
		return 1;
	else if (n == 2) //n이 2일때 1,2,3의 합으로 나타내는 방법의 수
		return 2;
	else if (n == 3) //n이 3일때 1,2,3의 합으로 나타내는 방법의 수
		return 4;

	ret = 0;
	
	for (int i = 1; i <= 3; i++)
	{
		//숫자 i(1,2,3)을 선택하고 n-i을 1,2,3의 합으로 나타내는 방법을 구한다
		ret += solve(n - i);
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	//cache를 -1로 초기화 한다
	memset(cache, -1, sizeof(cache));

	int testcase;
	int n;
	int result;

	cin >> testcase;

	for (int t = 0; t < testcase; t++)
	{
		cin >> n;
		result = solve(n);
		cout << result << "\n";
	}

	return 0;
}