[백준/C++] 9095번_1, 2, 3 더하기

문제는 다음과 같습니다.

먼저 초항을 구하면 다음과 같습니다.
n=1일때는 만들 수 있는 경우가 (1) 1가지입니다. a(1)=1
n=2일때는 (1, 1), (2)로 2가지입니다. a(2)=2
n=3일때는 (1,1,1), (1,2),(2,1), (3)로 4가지입니다. a(3)=4

정리하면 아래와 같습니다.

n=1, a(1)=1
n=2, a(2)=2
n=3, a(3)=4

다음으로 점화식의 규칙을 찾아보면,
정수 n을 입력받았을 때,
나열된 마지막 수가 1, 2, 3 세 가지 경우로 나눠볼 수 있습니다.

• 입력받은 마지막 수가 1인 경우: a(n-1) + <마지막 수 1>
• 입력받은 마지막 수가 2인 경우: a(n-2) + <마지막 수 2>
• 입력받은 마지막 수가 3인 경우: a(n-3) + <마지막 수 3>

따라서 정수 n(n>=4)에 대한 점화식은 다음과 같이 나타낼 수 있습니다.

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

전체 코드는 다음과 같습니다.

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

int a[11]={0, };

int func(int num){
  if(a[num]) return a[num];

  return a[num]=func(num-1)+func(num-2)+func(num-3);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    a[1]=1;
    a[2]=2;
    a[3]=4;
    int t, n;
    cin>>t;
    for(int i=0; i<t; i++){
      cin>>n;
      cout<<func(n)<<"\n";
    }
    
    return 0;
}

2/5 토요일 복습)

과거의 저는 top-down을 좋아했나봅니당🤣
왜 이제는 bottom-up방식을 선호하는 걸까요..?
이번에도 복습에서는 bottom-up 방식을 이용하였습니다.
풀이는 다음과 같습니다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int dp[11]={0, }; int n, tmp; cin>>n;
    dp[1]=1; dp[2]=2; dp[3]=4;

    for(int i=4; i<11; i++){
      dp[i]=(dp[i-1]+dp[i-2]+dp[i-3]);
    }

    for(int i=0; i<n; i++){
      cin>>tmp;
      cout<<dp[tmp]<<"\n";
    }

    return 0;
}