합을 나타낼 때는 수를 1개 이상 사용해야 한다.
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를
구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고,
정수 n이 주어진다. n은 양수이며 11보다 작다.

제한 조건

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이 내용

먼저 이번 문제를 동적 프로그래밍 방식으로 풀기 위해 재귀로 구현 할 것이며, memo라는 변수에 n을 합으로 나타내는 수를 저장할 것이다.

문제를 읽어보면 1, 2, 3의 합으로 나타내는 방법의 수라는 말이 있다.
이 말을 생각해보며 4를 합으로 나타내는 과정을 만들어보겠다.

(이 경우들이 잘 이해가 안된다면 문제 설명에서의 1, 2, 3의 합으로 나타내는 방법을 생각 해보자)

설명한것과 똑같이 4, 3, 2를 합으로 나타낼수 있는 값을 모두 더하면 5를 나타낼 수 있는 값이 나온다.
1+4에서 4는 합으로 나타낼수 있는 값이 아니므로 1+(1+3), 1+(2+2), 1+(3+1) 과 같은 형태가 된다.

if (n==1){...} else if (n==2){...} else if(n==3){...}
1,2,3은 표현할 수 있는 가장 작은 단위이므로 값을 바로 리턴 해주도록 하였다.

int ret = dp(n - 1) + dp(n - 2) + dp(n - 3);
n이 5일때 n-1, n-2, n-3은 4, 3, 2가 된다. 이말은 (1+4), (2+3), (3+2)로 볼 수 있다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int memo[1000];

int dp(int n)
{
    int &memoVal = memo[n];

    if (n == 1)
    {
        return 1;
    }
    else if (n == 2)
    {
        return 2;
    }
    else if (n == 3)
    {
        return 4;
    }

    if (memoVal != -1)
    {
        return memoVal;
    }

    int ret = dp(n - 1) + dp(n - 2) + dp(n - 3);

    memoVal = ret;

    return ret;
}

int main()
{
    memset(memo, -1, sizeof(memo));

    int t;
    cin >> t;

    int arr[11];
    for (int i = 0; i < t; i++)
    {
        cin >> arr[i];
        memo[i] = -1;
    }

    for (int i = 0; i < t; i++)
    {
        cout << dp(arr[i]) << "\n";
    }
}

문제 설명

백준 9095번 계단 오르기

입력

제한 조건

풀이 내용