[백준 BOJ][C++]9095번 1, 2, 3 더하기 풀이: DP

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

9095번: 1, 2, 3 더하기

 

 이 문제는 Dynamic Programming 을 이용하여 해결할 수 있습니다. 

 

숫자 N	모든 경우	경우의 수  dp[N]
1	=1	1
2	=1+1 =2	2
3	=1+1+1 =1+2 =2+1 =3	4
4	=1+3 (3=1+1+1    =1+2    =2+1    =3) =2+2 (2=1+1    =2) =3+1 (1=1)	7 =dp[1]+dp[2]+dp[3]
5	=1+4 (4=1+1+1+1    =1+1+2    =1+2+1    =2+1+1    =2+2    =1+3    =3+1) =2+3 (3=1+1+1    =1+2    =2+1    =3) =3+2 (2=1+1    =2)	13 =dp[2]+dp[3]+dp[4]

 

 위 표를 보시면 숫자 N을 1, 2, 3의 합으로 나타내는 경우의 수는 N에서 각각 1, 2, 3을 뺀 값에 대한 수에 대한 경우의 수들의 합입니다. 

 

 dp[n]을 숫자 n을 1, 2, 3의 합으로 나타낸 경우의 수라고 하면,

 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] ,  (n>3) 이 됩니다. 

 

#include<iostream>

using namespace std;

int dp[11] = { 0, };

int main(void) {

	int t, n;

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	cin >> t;

	while (t > 0) {

		cin >> n;

		if (dp[n] != 0) {
			cout << dp[n] << endl;
		}
		else {
			for (int i = 4; i <= n; i++) {
				dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
			}

			cout << dp[n] << endl;
		}

		t--;
	}


	return 0;
}