문제

문제 출처

문제 해결 전략

[1, 2, 3]을 이용하여 입력으로 받은 값의 합을 구하는 경우의 수를 계산해야 한다.

1을 계산하는 경우의 수
=> 1가지

2을 계산하는 경우의 수
1 + 1
2
=> 2가지

3을 계산하는 경우의 수
1 + 1 + 1
2 + 1
1 + 2
3
=> 4가지

T1 + T3 / T2
4를 계산하는 경우의 수
1 + 1 + 1 + 1

2 + 1 + 1
1 + 2 + 1
1 + 1 + 2

2 + 2

1 + 3
3 + 1

=> 7가지

5를 계산하는 경우의 수
1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1
1 + 2 + 1 + 1
1 + 1 + 2 + 1
1 + 1 + 1 + 2

2 + 1 + 2
1 + 2 + 2
2 + 2 + 1

3 + 1 + 1
1 + 1 + 3
1 + 3 + 1

3 + 2
2 + 3
=> 13가지

6을 계산하는 경우의 수
1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
1 + 1 + 2 + 1 + 1
1 + 1 + 1 + 2 + 1
1 + 1 + 1 + 1 + 2

2 + 2 + 1 + 1
2 + 1 + 2 + 1
2 + 1 + 1 + 2
1 + 2 + 1 + 2
1 + 1 + 2 + 2
1 + 2 + 2 + 1

3 + 1 + 1 + 1
1 + 3 + 1 + 1
1 + 1 + 3 + 1
1 + 1 + 1 + 3

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

2 + 2+ 2
3 + 3
=> 24가지

점화 식을 세워 보면
Tn = Tn-1 + Tn-2 + Tn-3

예를 들어서 5를 구하는 경우의 수는
T5 = T4 + T3 + T2

코드

#include<iostream>
using namespace std;

int num[10+1] = {0, 1, 2, 4, };

int sumT(int n){
	if(n == 1 || n == 2|| n == 3) return num[n];
	else if(num[n] == 0) num[n] = sumT(n-1) + sumT(n-2) + sumT(n-3);
	return num[n];
}
int main(){
	int t; cin >> t;
	for(int i = 0;i < t;i++){
		int n; cin >> n;
		cout << sumT(n) << endl;
	}
	//for(int i = 1;i < 11;i++) cout << sumT(i) << endl;

}