23.04.21. 풀었던 문제들

Leetcode 879. Profitable Schemes

 또 그놈의 3D DP이다. 문제를 보고 일단 knapsack같은 문제인가? 라고 생각했다. 일단 문제 조건이 n=100으로 아주 널널한 편이어서 아마 3D DP일 거라 생각했다. 100 * 100 * 100은 백만으로 딱 $n^3$으로 적당히 풀리는 문제니까.

 

첫 번째 접근

 그래서 dp[i][j][k]를 세우고 어떤 식일까 유추했다.

• i부터 j까지 k명 썼을 때 가능한 개수? 음... 모든 case에 대해 각 case가 얻은 profit을 얻어야 다음 경우를 계산할 수 있다. 기각.
• i부터 j까지 k원 썼을 때 가능한 개수? 음.. 모든 case에 대해 각 case가 몇 명을 사용했는지가 있어야 다음 경우를 계산할 수 있다.
• 그러면 변수가 [어떤plan까지 사용했는지], [몇 명을 사용했는지], [얼마의 profit을 얻었는지] 3개로 추려진다. 3차원이니까 [어떤 plan을 사용했는지]는 0부터 i까지 plan을 봤다고 생각해야 할 것이다.

 일반적으로 이런 DP 문제의 항은 문제에서 주어진 대로 구성되는 경우가 많다. 따라서 dp[i][j][k]를 [plan index 0부터 i까지 봤을 때, j명 사용했을 때, k원 이상을 번 경우의 수] 라고 정의하자.

 

 그러면 i-1번째 plan을 이용해 i번째 plan을 계산할 때, i-1을 쓰는 경우가 있고, 쓰지 않는 경우가 있을 것이다.

• 쓰지 않는 경우는 dp[i][j][k] = dp[i-1][j][k]이다. i-1번째 plan까지 봤을 때 사용한 명수, 번 돈은 변화가 없기 때문
• 쓰는 경우는 dp[i][j][k] = dp[i-1][j-group[i]][k-profit[i]]이다. i-1번째 plan을 사용했기 때문에 사용한 명수, 번 돈에 변화가 생기기 때문이다.
• dp[i][j][k]는 이 둘의 합이 될 것이다.

 

 여기까지 봤을 때, knapsack과 그냥 똑같은 문제임을 알 수 있다. 다만, knapsack은 변화하는 인수가 하나라 2d dp이지만 여기서는 변화하는 인수가 2개라서 3d dp로 풀리는 것이다.

 

 이 때, j-group[i]와 k-profit[i]가 음수가 되는 경우를 생각해야 한다.

•  i-1번째 plan을 사용하는 경우, j-group[i]는 항상 0 이상이 되어야 한다. i번째 plan을 pickup 할 수 있어야 하기 때문이다. j-group[i]가 음수라면 그만큼 사람이 부족하다는 것이므로 선택할 수 없다. ... 1
•  마찬가지로 k-profit[i]가 음수일 경우 0으로 바꾸면 된다 0원 이하를 사용하는 경우의 수는 항상 0원을 사용하는 경우의 수와 동일하기 때문이다. ... 2

 

 그러면 초기값은 dp[0][0][0] = 1로 설정하면 된다. 0명으로 0원 이상을 사용하는 가능한 경우의 수는 아무것도 고르지 않는 경우인 1이기 때문이다.

 

 마지막으로 정답은, dp[i][j][k]를 [plan index 0부터 i까지 봤을 때, j명 사용했을 때, k원 이상을 번 경우의 수] 라고 정의했기 때문에 plan index를 끝까지 봤을 때, k가 minProfit일 때 모든 j에 대한 합이 된다. ... 3

 

// Runtime 375 ms Beats 15.9%
// Memory 53.9 MB Beats 27.83%

class Solution {
public:
    int MOD = 1e9 + 7;
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int planSize = group.size();
        vector<vector<vector<int>>> dp(planSize + 1, vector<vector<int>>(n+1, vector<int>(minProfit + 1, 0)));

        dp[0][0][0] = 1;
        for(int i = 1; i<=planSize; i++){
            for(int j = 0; j<=n; j++){
                for(int k = 0; k<=minProfit; k++){
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= group[i-1]){ // ... 1
                        int newK = k-profit[i-1] <= 0 ? 0 : k-profit[i-1]; // ... 2
                        dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-group[i-1]][newK]) % MOD;
                    }
                }
            }
        }

        int answer = 0;
        for(int j = 0; j<n+1; j++){ // ... 3
            answer = (answer + dp[planSize][j][minProfit]) % MOD;
        }
        return answer;
    }
};

 

시간복잡도

 group.size()를 G, minProfit을 P로 표현했을 때 n * G * P의 3중 for문을 순회하므로 O(nGP)이다.

 

공간복잡도

 n * G * P size의 3d array를 모두 채워야 하므로 O(nGP)이다.

 

 

두 번째 접근 : space optimization

 코드를 보면 dp[i]는 항상 dp[i-1]에 depend하는 것을 볼 수 있다. 또한 j, k는 항상 자신보다 더 작은 값에 의존한다. 따라서 i * j * k로 이루어진 3d array를 j * k의 2d array로 만들 수 있다.

 단, j와 k는 항상 자신보다 더 작은 값에 의존하고 있으므로 j, k의 탐색은 큰 것에서부터 작은 것으로 탐색해야 한다.

// Runtime 232 ms Beats 40.9%
// Memory 9 MB Beats 90.9%

class Solution {
public:
    int MOD = 1e9 + 7;
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int planSize = group.size();
        vector<vector<int>> dp(n+1, vector<int>(minProfit + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i<=planSize; i++){
            for(int j = n; j>=0; j--){ // *** 주의 : 역순으로 진행해야 함
                for(int k = minProfit; k>=0; k--){
                    if(j >= group[i-1]){
                        int newK = k-profit[i-1] <= 0 ? 0 : k-profit[i-1];
                        dp[j][k] = (dp[j][k] + dp[j-group[i-1]][newK]) % MOD;
                    }
                }
            }
        }

        int answer = 0;
        for(int j = 0; j<n+1; j++){
            answer = (answer + dp[j][minProfit]) % MOD;
        }
        return answer;
    }
};

 

시간복잡도

 group.size()를 G, minProfit을 P로 표현했을 때 n * G * P의 3중 for문을 순회하므로 O(nGP)이다.

 

공간복잡도

 n * P size의 2d array를 모두 채워야 하므로 O(nP)이다.

 

 

 

후기

 3d dp는 너무 빡세다 ㅠㅠ 오늘 거는 그래도 풀만했다.