[BOJ] 9095. 1, 2, 3 더하기

문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

---

풀이

 

n 번째에서 1,2,3의 합으로 이루어진 경우는
n-1 번째에서 각각의 값에 1을 더하는 경우
n-2 번째에서 각각의 값에 2를 더하는 경우
n-3 번째에서 각각의 값에 3을 더하는 경우로 나타낼 수 있다.

-> f(n) = f(n-1) + f(n-2) + f(n-3)

---

코드

#include<iostream>
using namespace std;

int DP[11];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	DP[1] = 1;
	DP[2] = 2;
	DP[3] = 4;
	int check;

	for (int N = 4; N <= 11; N++) DP[N] = DP[N - 1] + DP[N - 2] + DP[N - 3];

	for (int i = 0; i < T; i++) {
		cin >> check;
		cout << DP[check] << '\n';

	}

}