(4) [C++, Java] 백준 No.9095 : 1, 2, 3 더하기

문제

풀이

- 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-5-다이나믹-프로그래밍-문제-풀이4?category=864321

# C++(Top-down 방식)

#include <iostream>

using namespace std;

int d[12] = {1, 1, 2};   // d[0] = 1, d[1] = 1, d[2] = 2, d[4~11] = 0

// d[0] = 1; d[3] = 3인데 이게 정상적으로 작동하려면 d[0]=1이어야 하므로
// d[1] = 1; 원래 d[1]은 1이라서.
// d[2] = 2; 원래 d[2]은 2이라서.

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getAllCombiCount(int n)
{
    if (n <= 2)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        d[n] = getAllCombiCount(n-1) + getAllCombiCount(n-2) + getAllCombiCount(n-3);
        return d[n];
    }
}

int main()
{
    int T;
    cin >> T;

    while(T--){
        int n;
        cin >> n;
        cout << getAllCombiCount(n) << endl;
    }
}

# C++(Bottom-up 방식)

#include <iostream>

using namespace std;

int d[12] = {1, 1, 2};   // d[0] = 1, d[1] = 1, d[2] = 2, d[4~11] = 0

// d[0] = 1; d[3] = 3인데 이게 정상적으로 작동하려면 d[0]=1이어야 하므로
// d[1] = 1; 원래 d[1]은 1이라서.
// d[2] = 2; 원래 d[2]은 2이라서.

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getAllCombiCount(int n)
{
    if (n <= 2)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        for(int i=3; i <=n ; i++)
            d[i] = d[i-1] + d[i-2] + d[i-3];

        return d[n];
    }
}

int main()
{
    int T;
    cin >> T;

    while(T--){
        int n;
        cin >> n;
        cout << getAllCombiCount(n) << endl;
    }
}