[Leetcode 879]- Profitable Schemes (2023/04/21)

Fucked

There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime.

Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 10^9 + 7.

 

https://leetcode.com/problems/profitable-schemes/description/

Profitable Schemes - LeetCode

 

 

Constraints:

• 1 <= n <= 100
• 0 <= minProfit <= 100
• 1 <= group.length <= 100
• 1 <= group[i] <= 100
• profit.length == group.length
• 0 <= profit[i] <= 100

 

이번문제는 읽다가 잘못 이해해서 엄청 고생했네요...

 

Hint 1

문제 상황 + 제약 조건을 고려 했을 때, 완전 탐색으로 접근하자.

 

Hint 2

각 사건들에 대해, 선택 / 비 선택의 옵션을 가질 수 있다.

 

 

Approach 1 (DFS + Memoization)

 

1. 3차원 DP를 생성한다.

dp[i][j][k]

i : 사건 ( crime ) 

j : 고른 인원수 

k : 현재 profit

각 사건(i)에 대해서, 인원수 (j)를 선택하고, 이익 (k)를 선택한다.

var profitableSchemes = function(n, minProfit, group, profit) {
    const caseCnt = group.length;
    const MODULO = 10 ** 9 + 7;
    const dp = [...new Array(caseCnt)].map(() => [...new Array(n + 1)].map(() => new Array(minProfit + 1).fill(-1)));
};

 

2. 모든 사건을 순회했을 때, 현재 profit이 minProfit보다 크고 인원 수가  n을 넘지 않는다면, 올바른 경우이다.

var profitableSchemes = function(n, minProfit, group, profit) {
    const caseCnt = group.length;
    const MODULO = 10 ** 9 + 7;
    const dp = [...new Array(caseCnt)].map(() => [...new Array(n + 1)].map(() => new Array(minProfit + 1).fill(-1)));
    
	function process(i, j, k) {
    	if(j > n){ // 당연하지만, 고른 멤버수가 총 멤버수를 넘는건 제외
            return false
        }
        if (i === caseCnt){
        	if(j <= n && k >= minProfit){
            return true;
            }
            return false
        }        
        if (dp[i][j][k] !== -1){ // 이미 갱신된 케이스에 대해선 연산할 필요가 없으므로
        	return dp[i][j][k]
        }
    }
    return process(0, 0, 0);

};

3. 각 사건들을 선택 / 비선택 하는 경우로서 분기한다.

var profitableSchemes = function(n, minProfit, group, profit) {
    const caseCnt = group.length;
    const MODULO = 10 ** 9 + 7;
    const dp = [...new Array(caseCnt)].map(() => [...new Array(n + 1)].map(() => new Array(minProfit + 1).fill(-1)));
    
	function process(i, j, k) {
    	if(j > n){
            return false
        }
        if (i === caseCnt){
        	if(j <= n && k >= minProfit){
            return true;
            }
            return false
        }        
        if (dp[i][j][k] !== -1){
        	return dp[i][j][k]
        }
        
        // 해당 사건을 넘기는 경우 ( i + 1 로써, 지나치면됨 )
        let notTake = process(i + 1, j, k);
        
        //해당 사건을 픽하는 경우 ( i + 1 로 다음 사건으로 넘어가고, j + group[i] 로써, 사건에 참여하는 사람 수를 증가시킨다.
        let take = process(i+1 , j + group[i] , Math.min(minProfit, k + profit[i]))
        return dp[i][j][k] = (notTake + take) % MODULO;
    }
    return process(0, 0, 0);

};

 

Approach 2 (Tabulation)

https://www.youtube.com/watch?v=MosNqLOkJ3Y&t=1114s 보고 이해하긴했는데.. 이렇게 풀라하면 아직 생소해서 그런지 못풀거 같네요..

 

 

var profitableSchemes = function(n, minProfit, group, profit) {
    const caseCnt = group.length;
    const MODULO = 10 ** 9 + 7;
    const dp = [...new Array(caseCnt + 1)].map(() => [...new Array(n + 1)].map(() => new Array(minProfit + 1).fill(0)));
    dp[0][0][0] = 1
	
    for(let i = 1 ; i <= caseCnt; i ++){
        const selectedGroupMember = group[i - 1];
        const selectedProfit = profit[i - 1];
        for (let j = 0; j <= n; j++) {
            for(let k = 0; k <= minProfit ; k ++){
                //case 1: not select case i
                dp[i][j][k] = dp[i - 1][j][k];

                //case 2: select case i
                if(j >= selectedGroupMember){
                    dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-selectedGroupMember][Math.max(0, k - selectedProfit)]) % MODULO
                }
            }
        }
    }
   
    let sum = 0;
    for(let i = 0; i <= n ; i ++){
        sum = (sum + dp[caseCnt][i][minProfit]) % MODULO
    }
    return sum;

};