백준 9095번: 1, 2, 3 더하기

[문제 링크]

9095번: 1, 2, 3 더하기

---

간단한 DP 문제였다.

n을 1, 2, 3의 합으로 나타내는 방법의 수를 계산하는 함수를 Sol(int n) 이라고 할 때,

n이 10일 때 나올 수 있는 방법의 수 Sol(10)은  Sol(9) + Sol(8) + Sol(7) 과 같다.

 

따라서 기저사례로 n == 0 또는 n == 1 일 때 1을 반환하도록 하여 방법의 수를 카운팅하고

(n == 0일 때 1을 반환하는 이유는 n이 2 또는 3일 경우 숫자의 합이 아닌 2, 3 그 자체로도 표현할 수 있기 때문) 

중복호출 되는 n을 메모이제이션하여 알고리즘을 구현하면 원하는 결과를 얻을 수 있다.

 

다른 방법으로는 n이 1, 2, 3 일 때 방법의 수를 사전에 메모라이징 해두고 기저사례를 조금 수정하면 동일한 결과를 얻을 수 있다.

---

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

int memo[11];

int Solution(int n)
{
	if (n == 0 || n == 1) return 1;

	int& ret = memo[n];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 1; i <= 3; i++)
		if (n - i >= 0) ret += Solution(n - i);
	
	return ret;
}

/*
int Solution2(int n)
{
	memo[1] = 1, memo[2] = 2, memo[3] = 4;

	if (n == 1 || n == 2 || n == 3) return memo[n];

	int& ret = memo[n];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 1; i <= 3; i++)
		ret += Solution(n - i);

	return ret;
}
*/
int main(void)
{
	memset(memo, -1, sizeof(memo));
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		cout << Solution(n) << endl;
	}
	
	return 0;
}

알고리즘 200일 프로젝트 - 63 day