[백준 15989] 1,2,3 더하기 4

문제 : 1,2,3 더하기 4

문제 유형 : 다이나믹 프로그래밍

이 문제는 1,2,3 더하기로 표현하는 것들 중에서 더하기 순서를 바꿨을때랑 같은 것을 한 종류로 보는 문제이다. 4를 가지로 예를 들어보자.
4를 1,2,3더하기로 표현해보면

3+1
2+2
1+3
2+1+1
1+2+1
1+1+2
1+1+1+1

이렇게 7가지가 있는데 더하기 순서를 바꾸면 같아지는것을 묶어보자.

3+1 (1+3)
2+2
2+1+1 (1+2+1, 1+1+2)
1+1+1+1

이렇게 4가지가 있다. 이것을 어떻게 수식으로 표현할까?

1,2,3 더하기 시리즈 문제는 모두 다이나믹 프로그래밍으로 풀 수 있다. 이를 재귀적으로 생각해보면 점화식이 보인다.

한 종류로 만들 때, 여러가지 순서 중 비오름차순으로 짜면 된다.

4를 가지고 예를 들어보자.

4에서 1,2,3을 빼면 모두 양수 이므로 아래와 같이 표현 할 수 있다.

3+□
2+□
1+□

그 다음에 □에는 뭐가 올 수 있을까?
바로 앞에서 사용한 숫자보다 작거나 같은 수가 오면 된다.

3+1
2+2
2+1+□
1+1+□

대충 하는 방법은 알겠지만 이를 가지고 어떻게 점화식을 세울지 안보인다. 그래서 난 표를 활용해봤다.

(핸드폰으로 표 그리는게 없네.....)

     1     2     3
1   1     0     0
2   1     1     0
3   1     1     1
4   ?      ?     ?
(세로축을 i, 가로축을 j로 하자)

표를 그리면 이런식으로 그릴 수 있다. 가로축은 더하기에서 사용할 1 2 3, 세로축에 있는 건 n이다. n의 값이 1 2 3일땐 금방 구할 수 있으니 초기값으로 깔아놓고 보자.
n==4일때 1로 시작하는 더하기는 몇개일까?

딱 하나밖에 없다. 1+1+1+1..

그럼 2로 시작하는 더하기는 몇개일까?
4에서 2를 빼보자. 그럼 2이다. 4에서 2를 뺐으니 2 이하로 된 수를 가지고 2를 만드는 갯수는 몇개일까?

바로 n==2(i==2)일때 j가 1,2일때 값을 더하면 된다.

즉 1+1 =2(DP[2][1]+DP[2][2])개이다.
실제로도 직접 계산해보면 같다는걸 알 수 있다.

이제 4에서 3을 빼보자. 그럼 1이다. 위랑 마찬가지로 1을 1이하로 된 수를 가지고 만들 수 있는 갯수는 1개이다. 즉 DP[1][1]이다.

핸드폰으로 작성해서 그런지 생각나는 대로 쓰느라 제대로 쓰고 있는지 잘 모르겠다.
아무튼, 위의 방법을 가지고 점화식을 세워보자.

i에서 3을 뺐을땐 DP[i][3]=DP[i-3][1]+DP[i-3][2]+DP[i-3][3]
DP[i][2]=DP[i-2][1]+DP[i-2][2]
DP[i][1]=DP[i-1][1]

이를 하나의 식으로 쓰면 아래와 같다.

#include<iostream>
 
using namespace std;
 
typedef long long ll;
int dp[10001][4];
 
int solve(int n, int k)
{
    if (dp[n][k])return dp[n][k];
    for (int i = 4; i <= n; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            int sum = 0;
            if (j == 1)
            {
                dp[i][j] = 1;
                continue;
            }
            for (int m = 1; m <= j; m++)
            {
                sum += dp[i - j][m];
            }
            dp[i][j] = sum;
        }
    }
    return dp[n][k];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
    for (; T--;)
    {
        int input;
        cin >> input;
        solve(input, 3);
        cout << dp[input][1] + dp[input][2] + dp[input][3] << '\n';
    }
    return 0;
}