[백준/C++] Adding 1s, 2s, and 3s

Adding 1s, 2s, and 3s

Integer 4 can be expressed as a sum of 1s, 2s, and 3s in seven different ways as follows:

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

Write a program that determines the number of ways in which a given integer can be expressed as a sum of 1s, 2s, and 3s. You may assume that the integer is positive and less than 11.

입력 The input consists of T test cases. The number of test cases (T ) is given in the first line of the input file. Each test case consists of an integer written in a single line.

출력 Print exactly one line for each test case. The line should contain an integer representing the number of ways.

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

Solution

It is optimal partial structure that divides current number n into 1s, 2s, and 3s each case. And there are many redundant subcases.
It means that this problem has to be solved by Dynamic Programming.

if I memo the number of ways in array D, D[i] should be contain the number of ways that can devide i into 1s, 2s, and 3s.
And number n is equal to 1 + (n-1) or 2 + (n-2) or 3 + (n-3).

It means that D[n - 1] is equal to the number of ways of 1 + (1s, 2s, and 3s).

In conclusion, D[n] = D[n - 1] + D[n - 2] + D[n - 3].

#include <iostream>
using namespace std;

int D[11] = {0};

int main()
{
	int T, n;
	cin >> T;

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

	while(T--) {
		cin >> n;
		cout << D[n] << "\n";
	}
	return 0;
}

The End