[백준] 1,2,3 더하기 9095번 (c++)

출처 : 9095번: 1, 2, 3 더하기 (acmicpc.net)

9095번: 1, 2, 3 더하기

해결 방법

dp 문제로 n을 1, 2, 3을 빼서 재귀 호출을 반복적으로 하며, n이 0 이면 return 1을 n이 음수면 return 0을 해서 기저 조건을 만들어 주었다.

dp table인덱스로는 숫자 n을 주었다.

#include <iostream>
#include <memory.h>
#include <algorithm>

using namespace std;
int dp[12];

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

	int& ret = dp[n];
	if (ret != -1) return ret;
	ret = 0;
	ret = f(n - 3) + f(n - 2) +f(n - 1);
	return ret;

}
int main() {
	memset(dp, -1, sizeof(dp));
	int C,n;
	cin >> C;
	while (C--) {
        cin >> n;
        cout << f(n) << endl;
	}
	return 0;
}