[알고리즘] 백준 9095번: 1, 2, 3 더하기 (C++), 아직도 어려운 점화식

아직도 DP의 문제를 푸는 데에 있어서 어려움을 겪는다. 그래도 전보다 나아진 것은 다음과 같다.

1. 작은 문제는 무엇이며 이 작은 문제들이 모여서 어떠한 큰 문제를 풀어야 하는지 탐색하려 한다.
2. 작은 문제들의 관계성에 중심을 두고 있다.
3. 어느 정도 코드의 구조를 알게 되었다. (감각의 관점)

그래서 이번 문제는 각 정수의 합을 나타낼 수가 몇 개가 있는지 적어보며 관계성을 파악하려 했다. 하지만, 규칙은 알 수가 있어도 어떠한 관계인가?라는 질문에는 정확한 대답을 내놓을 수 없었다.

 

풀이를 찾아보다가 다음의 풀이를 발견하게 되었다.

https://blog.naver.com/PostView.nhn?blogId=vjhh0712v&logNo=221470862600 

백준 알고리즘 9095번 문제풀이

 

이 포스팅에서 각 항들이 다음과 같은 관계를 가짐을 알 수 있었다.

정수가 4일 경우
1 + 3
2 + 2
3 + 1
로 나타낼 수가 있다.
이때 노란색으로 칠해진 부분들은 각각 몇 가지 경우로 나타낼 수 있는지만 파악하면 되었었다.

5의 경우에도 나타낼 수 있는 수는 1, 2, 3밖에 없으니

1 + 4
2 + 3
3 + 2
즉, 1 + (4가 가지는 경우의 수), 2 + (3이 가지는 경우의 수), 3 + (2가 가지는 경우의 수) 이 경우를 다 합치면 5가 가지는 경우의 수를 구할 수 있었다.

점화식으로 나타내면 이러하다.

a(n) = a(n - 1) + a(n - 2) + a(n - 3), (단, a(1) = 1, a(2) = 2, a(3) = 4)

아직도 점화식을 나타내기가 꽤 어렵다.

---

[코드]

#include <iostream>
#include <vector>
using namespace std;

int cache[12] = { 0, };
int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int n;
		cin >> n;
		cache[1] = 1;
		cache[2] = 2;
		cache[3] = 4;

		for (int i = 4; i <= n; i++) {
			cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3];
		}
		cout << cache[n] << '\n';
	}

	return 0;
}