1, 2, 3 더하기 4 15989

문제

접근 방법

	0	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4
3	1	1	2	3	4	5	7	8

동전 1이 생각나는 문제이다.
1차원 배열로 해결하고 싶지만 그렇게 하기 위해선 10,000까지를 한 번에 구해놓아야 하므로 시간제한을 넘을 것이라고 예상한다. (이전 테스트케이스를 재활용해야 하므로 2차원 배열로 해결하는 것이다)
2차원 배열로 해결하는 방식을 사용해야 한다.

코드

#include <iostream>
using namespace std;
int main()
{
    int T, min = 0;
    cin >> T;
    int dp[3][10001];
    int numbers[] = {2, 3};
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = min; i <= n; ++i)
        {
            dp[0][i] = 1;
            for (int number : numbers)
            {
                if (i - number >= 0)
                    dp[number - 1][i] = dp[number - 1][i - number] + dp[number - 2][i];
                else
                    dp[number - 1][i] = dp[number - 2][i];
            }
        }
        cout << dp[2][n] << "\n";
        if (min < n)
            min = n;
    }
    return 0;
}

풀이

1로 만드는 경우는 1 밖에 안 나오기에 DP[0][i]=1로 작성하였다.
이후 2, 3은 현재 배열에서 자신의 수만큼 뺀 값+이전 수 배열에서 사용한 값이라는 공식이 같기 때문에 배열로 해결해주었다.