1, 2, 3 더하기 (feat. 백준, 9095번)

1, 2, 3 더하기
https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/9095
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, arr[11] = { 0 };
	arr[0] = 0, arr[1] = 1, arr[2] = 2, arr[3] = 4;
	cin >> N;
	for (register int n = 0, v, i; n < N; ++n) {
		cin >> v;
		for (i = 4; i <= v; ++i)
			if (!arr[i])
				arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
		cout << arr[v] << endl;
	}
	return 0;
}
// *&)*@*

1. 1은 1로 1개입니다.
2. 2는 1+1, 2로 2개입니다.
3. 3은 1+1+1, 1+2, 2+1, 3로 4개입니다.
4. 4는 예제와 같이 7개 입니다.
5. 5는 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2 로 13개입니다.
6. 따라서 Ai = Ai-1 + Ai-2 + Ai-3 으로 수식이 성립됩니다.