BOJ 15989번 1, 2, 3 더하기 4

BOJ : https://www.acmicpc.net/problem/15989

github : https://github.com/junho0956/Algorithm/blob/master/15989/15989/%EC%86%8C%EC%8A%A4.cpp

 

문제를 풀고나서 다른분들의 코드를 참고해봤는데

다들 1차원 dp로 푸시던데 저는 1,2,3 크기인 3*n 형태의 2차원 dp로 해결하였습니다.

 

dp[i][num] 의 의미는

현재 숫자 i를 기준 num 을 만들수있는 경우의 수를 의미합니다.

dp 를 설명하기 위해 풀이를 천천히 해보겠습니다.

 

1,2,3 으로 임의의 수 num 을 만들기 위해서는 1,2,3 더하기 의 기본문제처럼 풀게되면

112 121 211 같은 합의 경우는 같은데 경우의 수는 다르게 두는 '중복' 이 발생하게 됩니다.

이런 중복을 모두 같은 경우의 수로 보려면 1, 2, 3 을 이용해서

내림차순으로 만들거나 오름차순으로 만드는 둘중 한가지의 방법을 선택해야 된다고 생각했습니다.

만약 오름차순으로 한다고 가정하고, 1과 2만 사용한다고 생각한다면

1 1 2 라는 경우가 생기지만 1 2 1 , 2 1 1 같은 경우는 생기지 않기 때문입니다.

마찬가지로 1 3 은 되지만, 3 1 은 만들어지지 않는다는 뜻입니다.

 

저는 이를 위에서 말씀드린 점화식 dp[i][num] : 현재 숫자 i로 num을 만들 수 있는 경우의 수로 표현하였고

코드를 보시면 아시겠지만 내림차순으로 해결하였습니다.

현재 숫자가 2 이면 2와 1만 사용하지 3은 사용하지 않게 되는 것입니다.

 

아래에서 num은 만들어야하는 수이고, stand 는 3,2,1 중 1가지 숫자가 됩니다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int n;
int dp[4][10001];
 
int dfs(int num, int stand) {
    // 중복없는 dfs를 만들어야 된다
    // 112 == 121 == 211 과 같은
    // 이럴 경우 오름차순 또는 내림차순에 의해서만 만들어지는 경우의 수를 구한다면 중복이 사라질 것이다
 
    if (num < 0) return 0;
    if (num == 0) return 1;
 
    int& res = dp[stand][num];
    if (res) return res;
 
    for (int i = stand; i >= 1; i--)
        res += dfs(num - i, i);
 
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int T; cin >> T;
 
    while (T--) {
        cin >> n;
        cout << dfs(n, 3)<< "\n";
    }
 
    return 0;
}