BOJ-9095 1,2,3 더하기

필요한 지식

1. 동적계획법

접근

• 점화식

dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
dp[i] : i를 1,2,3 의 합으로 나태내는 방법의 수

• i가 1,2,3 일경우 각각 1,2,4로 초기화 시켜준다.

코드(C++)

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int dp[15];
int go(int i) {
	if (i == 1) return 1;
	if (i == 2) return 2;
	if (i == 3) return 4;
	int& ret = dp[i];
	if (ret != -1) return ret;
	ret = 0;
	return ret = go(i - 1) + go(i - 2) + go(i - 3);
}
int main() {
	int n, x;
	scanf("%d", &n);
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		printf("%d\n", go(x));
	}
	return 0;
}