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

풀이:

a[n][0] : 3을 포함하지 않고, 2를 1개 이상 포함한 n 을 만드는 경우의 수

a[n][1] : 3을 1개 이상 포함한 n을 만드는 경우의 수

a[n][0] = a[n - 2][0] + 1

-> 2를 1개 이상 포함하여 n - 2 를 만드는 경우의 수에 2를 하나씩 더 붙힌 것

+ 1로만 이루어진 수에 2를 하나 붙힌 것)

a[n][1] = a[n - 3][1] + a[n - 3][0] + 1

-> 3을 3개 이상 포함하여 n - 3 을 만드는 경우의 수에 3을 하나씩 붙힌 것

+ 2를 1개 이상 포함하여 n - 3 을 만드는 경우의 수에 3를 하나씩 더 붙힌 것

+ 1로만 이루어진 수에 2를 하나 붙힌 것)

a[n][0] + a[n][1] + 1 (1로만 이루어진 경우의 수를 위해 1을 더해준다.)

코드:

사용언어 : c++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <iostream>
using namespace std;
int T, n, i = 3, a[10001][2];
int main() {
	cin >> T;
	a[2][0] = 1;
	while (T--) {
		cin >> n;
		for (; i <= n; i++)
			a[i][0] = a[i - 2][0] + 1, a[i][1] = a[i - 3][1] + a[i - 3][0] + 1;
		cout << a[n][0] + a[n][1] + 1 << endl;
	}
}