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

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

아주 기초적인 dp문제이다.

1, 2, 3만 사용할 수 있으므로 d[n]은 d[n-1]의 모든 경우의 수에 대하여 뒤에 1을 붙인 경우 + d[n-2]의 모든 경우에 대하여 뒤에 2를 붙인 경우 + d[n-3]의 모든 경우에 대하여 뒤에 3을 붙인 경우를 모두 더한 값을 갖는다. 

따라서 점화식은 d[n] = d[n-1] + d[n-2] + d[n-3] 이 된다.

#include <iostream>

using namespace std;

int d[12];

int dp(int n) {
	if (d[n] != 0) return d[n];
	return d[n] = dp(n - 1) + dp(n - 2) + dp(n - 3);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t, n;
	d[0] = 1;
	d[1] = 1;
	d[2] = 2;

	cin >> t;
	while (t--) {
		cin >> n;
		cout << dp(n) << '\n';
	}
	return 0;
}

메모리: 2016

시간: 0