문제 출처

1. 문제설명

  • 정수 n이 주어졌을 때,
  • n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라



2. 알고리즘 설계

  • DP 문제이다.
  • 점화식을 찾아야 하는데, 점화식이 생각보다 간단했다.
  • N-3, N-2, N-1번째의 경우의 수를 더해주면 N번째 경우의 수가 된다.



3. 로직

  • DP[N] = DP[N-1] + DP[N-2] + DP[N-3]
  • 테스트 케이스에 따라 계속 호출하는 것보다,
  • 한번 최대 크기까지 돌려놓는 게 더 효율적이라고 생각한다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int memo[11];

void DP(void) {
    memo[1] = 1;
    memo[2] = 2;
    memo[3] = 4;

    for (int i = 4; i <= 10; i++)
        memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3];
}

int main(void) 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    DP();
    int TC; cin >> TC;
    while (TC--) {
        int n; cin >> n;
        cout << memo[n] << '\n';
    }

    return 0;
}