[백준 9764번] 서로 다른 자연수의 합 (C++)

https://www.acmicpc.net/problem/9764

9764번: 서로 다른 자연수의 합

중복된 자연수를 사용할 수 없기 때문에 우리가 흔히 아는 동전 문제와 비슷하게 생각할 수 있지만 살짝 다르다.

동전 문제는 button up으로 간단하게 해결 할 수 있다. 하지만 이 문제는 buttom up 보다는 top down이 더 효율적이고 풀이도 간단한 문제이다. 두 풀이를 모두 올리니 공부할 때 참고 하면 되겠다.

 

먼저 Dp 이므로 큰 문제(우리의 목표)를 작은 문제로 나눠야 한다. 동전 문제에서는 2000원이 되는 경우를 1원이 되는 경우, 2원이 되는 경우, ..., 2000원이 되는 경우까지 바로 도달 할 수 있었다. 같은 동전을 중복해서 사용할 수 있기 때문에 특정 동전으로 특정 금액을 만드는 경우를 하나씩 누적해 가며 Dp값을 갱신시켜 나갔다.

이 문제는 1을 가지고 2000을 만들 수 있는 경우, 1~2를 가지고 2000을 만들 수 있는 경우, 1~3을 가지고 2000을 만들 수 있는 경우, ... , 1~2000을 가지고 2000을 만들 수 있는 경우까지 생각해야 한다. (당연의 각 숫자는 최대 한번씩 밖에 사용하지 못한다.)

 

1. Buttom-Up

Dp table을 2차원으로 설정하여 dp[i][j] = 1~j를 가지고 i를 만들 수 있는 경우의 수로 생각한다.

1. j > i 이면 dp[i][j] = dp[i][j-1]로 이전 dp값과 같다.(j가 아무리 커져봐야 i보다 크면 더 이상의 경우수가 생기지 않기 때문)

2. j <= i 이면 dp[i][j] = dp[i][j-1] + dp[i-j][j-1] 이다.

 

예를 들어보자, dp[5][4]를 구하고 싶다.(1~4를 이용하여 5를 구하는 경우)

dp[5][4] = dp[5][3](1~3을 이용하여 5를 구하는 경우) + dp[1][3](1~3을 이용하여 1을 구하는 경우)이다.

우선 1~4를 이용하여 5를 구하는 경우에다가 4가 무조건 들어가는 경우는 더해주면 되는 것이다. 4가 무조건 들어가려면 5-4=1이므로 1을 구하는 방법을 구하면 되는 것이다.

사실 5를 구하는 방법인데 4를 이미 사용한거나 다름 없으므로 1~3을 이용해 1을 구하는 방법을 구하면 최종 1~4를 이용해 5를 구하는 방법이 구해지게 된다. 

 

위의 예시와 같은 방법으로 2000까지 구해서 테스트 케이스들을 모두 돌려주면 된다.

코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
#define MOD 100999
#define endl "\n"
using namespace std;

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int t, n;
    int dp[2001][2001];
    dp[0][0] = 1;
    for(int i = 1; i < 2001; i++){
        dp[i][0] = 0;
        dp[0][i] = 1;
    }
    for(int i = 1; i < 2001; i++){
        for(int j = 1; j < 2001; j++){
            if(i<j){
                dp[i][j] = dp[i][j-1];
                continue;
            }
            dp[i][j] = (dp[i][j-1] + dp[i-j][j-1]) % MOD;
        }
    }

    cin >> t;
    while(t--){
        cin >> n;
        cout << dp[n][n] << endl;
    }
}

 

 

벌써부터 점화식이 if문을 통해 2개로 나뉘고 복잡하다. 다음 Top-down방식을 봐보자.

2. Top-Down

개념은 buttom-Up이랑 같은데 Top에서 부터 시작하면 DP배열이 1차원으로도 충분하다.

(i를 1~j까지의 숫자로 만드는 경우)를 생각하면 된다.

 

코드는 다음과 같다.

#include <iostream>
#define endl "\n"
using namespace std;
int main(){
    int t,n;
    cin >> t;
    int dp[2001] = {1,};
    for(int i = 1; i < 2001; i++){
        for(int j = 2000; j >= i ; j--){
            dp[j] = (dp[j] + dp[j-i])%100999;
        }
    }
    while(t--){
        cin >> n;
        cout << dp[n] << endl;
    }
}

 

 

bottom-up보다 코드도 훨씬 짧고, 메모리도 적게 든다.

 

 

모든 문제에서 Top-down이 Bottom-up 보다 효율적인 것은 아니다. 보통은 대게 Buttom-up이 효율적이라고 한다.

하지만 Dp를 처음 접하는 사람이라면 Top-down으로 사고하는 연습이 dp를 이해하는데 많은 도움이 된다.