알고리즘 :: 백준 :: DP :: 9095 :: 1, 2, 3 구하기

문제

정수 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 이라는 작은 문제로 분해할 수 있다.
• 점화식은 $D(n) = D(n - 1) + D(n-2)+D(n-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';
    }
}

결과