[baekjoon 9095] 1, 2, 3 더하기 - DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

#include <iostream>
using namespace std;

int arr[12] = {0, 1, 2, 4, };
int T,n;

int dp(int n) {
	if (n <= 3) {
		return arr[n];
	}
	else{
		if (arr[n]) {
			return arr[n];
		}
		else {
			return arr[n] = dp(n - 1) + dp(n - 2) + dp(n - 3);
		}
	}
}

int main() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> n;
		cout << dp(n) << "\n";;
	}
}

점화식은 N = N-1 + N-2 + N-3으로 

 

만약 N = 14 이면

(1) 13을 만드는 경우의 수들의 조합에 각 + 1 (13+1 = 14)

(2) 12를 만드는 경우의 수들의 조합에 각 + 2 (12+2 = 14)

(3) 11을 만드는 경우의 수들의 조합에 각 + 3 (11+3 = 14) 을 더해주는 경우와 같다.