🖊️ 문제

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

---

🖊️ 문제

이번에도 dp
dp지옥에서 빠져나오기 위해서 열심히 짱구를 굴렸는데 ....

흠ㅎ.....
진짜 열심히 분석해봤다

1 : 1
2 : 11, 2 -> 2
3 : 111, 12, 21, 3 -> 4
4 : 1111, 112, 121, 211, 13, 31, 22 -> 7
5 : 11111, 1112, 1121, 1211, 2111, 122, 212, 221, 113, 131, 311, 23, 32 -> 13
6 : 111111, 11112, 11121, 11211, 12111, 21111, 1122, 1212, 1221, 2211, 2121, 2112, 1113, 1131, 1311, 3111, 123, 132, 213, 231, 312, 321, 23, 32 -> 24
7 : 44
8 : 81

흠..
1 2 4 7 13 24 44 81

여기서 연관성을 찾다가
포기했는데

끈 기 를 가 져 야 지 수 민 아 제 발 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

다왔는데 너무 슬펐다.

무려무려 ..
a[i] = a[i-1] + a[i-2] + a[i-3]
히힣

반성하자
끈기를 가지자.

반성의 의미로 오늘 dp 2개 더 풀기로.

#include <iostream>
using namespace std;

int arr[11];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int t;
	cin >> t;

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

	for (int tk = 0; tk < t; tk++) {
		int n;
		cin >> n;
		cout << arr[n] << endl;
	}
}