C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 9095번:1,2,3 더하기 답

계단 오르기 문제입니다 -> 전형적인 메모이제이션 즉 동적할당법에 해당하는 문제입니다.

먼저 점화식은 f(n) = f(n-3)+f(n-2)+f(n-1)입니다.

#include <iostream>
using namespace std;
int Plus(int num)
{
    static int mem[11];//배열선언
    if (mem[num-1] != 0)//이미 있는 항이라면 바로 그 값 반환
    {
        return mem[num-1];
    }
    if (num == 1)
    {
        return mem[num-1] = 1;
    }
    if (num == 2)
     {
         return mem[num-1] = 2;
     }
    if (num == 3)
     {
         return mem[num-1] = 4;
     }
     return mem[num-1] = Plus(num - 3) + Plus(num - 2) + Plus(num - 1);//배열에 없는 새로운 항이라면 다음과 같은 점화식 적용
}
int main(){
 
    int T,num;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> num;
        cout << Plus(num) << '\n';
    } 
 
}