정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
6
까지는 손으로 계산할 수 있지만 그렇게 한다면 1, 2, 3, 4, 5, 6
각 숫자 사이의 규칙성을 찾기 힘들 것이다.4, 5
에서 규칙성을 찾아내더라도 6
에서도 통할 것이라는 보장을 할 수 없다.n
을 1, 2, 3의 합으로 나타내는 방법의 수를 기록한다면 규칙성을 찾아내지 않아도 빠르게 계산할 수 있으므로 DP가 유효하다.n
은 (n - 1) + 1
, (n - 2) + 2
그리고 (n - 3) + 3
이라는 작은 문제로 분해할 수 있다.#include <iostream>
#include <cstring>
using namespace std;
static int loop = 0, n = 0;
static int cache[11];
int solve(int num) {
if (num == 0) return 1; // [중요!] 0을 공집합 1로 쳐야한다.
if (num == 1 || num == 2) return num; // [기저] num=1, 2일때 방법이 num과 같다.
if (cache[num] > 0) return cache[num];
// 점화식 - D(N) = D(N-1) + D(N-2) + D(N-3)
return cache[num] = solve(num - 1) + solve(num - 2) + solve(num - 3);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> loop;
memset(cache, 0, sizeof(cache));
while (loop--) {
cin >> n;
cout << solve(n) << '\n';
}
}