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

 

문제 URL:

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

다음 문제는 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제로, 

다이나믹 프로그래밍을 사용하여 문제를 풀었다. 

 

현재 숫자가 n일 때 n은

1+(n-1)

2+(n-2)

...

(n-3)+3

(n-2)+2

(n-1)+1

다음과 같이 만들어 질 수 있다. 

 

이때, 1, 2, 3만을 이용하여 n을 만들어야하기 때문에 

1, 2, 3을 이용하여 n-1, n-2, n-3을 만드는 각각의 경우의 수(DP)를 모두 더해주면

1, 2, 3을 이용하여 n을 만드는 방법의 수를 구할 수 있다. 

---

#include <iostream>
using namespace std;

int T, n;
int DP[11];

int main() {
	DP[1] = 1;
	DP[2] = 2;
	DP[3] = 4;

	cin >> T;

	while(T--) {
		cin >> n;

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

		cout << DP[n] << "\n";
	}

	return 0;
}