갱단에 G명의 멤버가 있고, 저지를 결정할 수 있는 다양한 범죄 목록이 주어져 있다고 가정해 보겠습니다. i번째 범죄는 profit[i]만큼의 이익을 창출하며, 실행하는 데 group[i]명의 멤버가 필요합니다.
한 멤버가 어떤 범죄에 참여하고 있다면 다른 범죄에는 동시에 참여할 수 없습니다. 여기서 수익성 있는 계획(profitable scheme)이란, 선택한 범죄들의 부분집합이 창출하는 총 이익이 최소 P 이상이고, 해당 부분집합에 참여하는 총 멤버 수가 G 이하인 경우를 말합니다.
우리가 구해야 할 값은 이런 계획이 총 몇 가지나 가능한지입니다. 답은 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 G = 5, P = 3, group = [2, 2], profit = [2, 3]이라면 출력은 2입니다. 이익이 3인 두 번째 범죄만 선택하는 경우와 두 범죄를 모두 선택하는 경우, 이렇게 두 가지 계획이 조건을 만족하기 때문입니다.
풀이 접근 방식
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '투입된 멤버 수'와 '달성한 이익'이라는 두 가지 상태를 동시에 추적하는 2차원 DP 테이블을 구성하는 것입니다.
- 정답을 누적할 변수 ret을 0으로 초기화합니다.
- (G + 1) × (P + 1) 크기의 2차원 배열 dp를 선언합니다. dp[i][j]는 'i명의 멤버를 사용해 이익 j(단, P를 초과하면 P로 간주)'를 달성한 계획의 수를 의미합니다.
- 아무 범죄도 선택하지 않은 초기 상태 dp[0][0]을 1로 설정합니다.
- 각 범죄 k에 대해 p = profit[k], g = group[k]를 가져온 뒤, i를 G − g부터 0까지, j를 P부터 0까지 역순으로 순회하며 다음을 수행합니다.
dp[i + g][min(P, j + p)] += dp[i][j]
dp[i + g][min(P, j + p)] %= m - 마지막으로 i를 0부터 G까지 순회하며 ret에 dp[i][P]를 더하고, 매 단계마다 m으로 나머지 연산을 적용합니다.
- ret을 반환합니다.
역순 순회와 이익 상한 처리가 중요한 이유
i와 j를 감소시키며 순회하는 것은 같은 범죄가 여러 번 중복 선택되는 것을 막기 위함입니다. 이는 0/1 배낭 문제(0/1 Knapsack)에서 사용하는 표준 기법으로, 정방향으로 순회하면 이미 갱신된 값을 다시 읽어 잘못된 결과가 나올 수 있습니다.
또한 이익을 min(P, j + p)로 상한 처리하면 P 이상의 이익은 모두 동일하게 취급되므로 테이블 크기를 (G + 1) × (P + 1)로 제한할 수 있고, 인덱스 초과 오류도 자연스럽게 방지됩니다. 시간 복잡도는 O(n × G × P), 공간 복잡도는 O(G × P)입니다(n은 범죄의 개수).
C++ 구현 예제
위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
int profitableSchemes(int G, int P, vector<int> &group, vector<int> &profit) {
int ret = 0;
vector<vector<int>> dp(G + 1, vector<int>(P + 1));
dp[0][0] = 1;
for (int k = 0; k < group.size(); k++) {
int p = profit[k];
int g = group[k];
for (int i = G - g; i >= 0; i--) {
for (int j = P; j >= 0; j--) {
dp[i + g][min(P, j + p)] += dp[i][j];
dp[i + g][min(P, j + p)] %= m;
}
}
}
for (int i = 0; i <= G; i++) {
ret += dp[i][P];
ret %= m;
}
return ret;
}
};
int main() {
Solution ob;
vector<int> v = {2, 2}, v1 = {2, 3};
cout << ob.profitableSchemes(5, 3, v, v1);
}입력
5, 3, [2,2], [2,3]
출력
2
실행 결과 2가 출력되며, 이는 앞서 살펴본 두 가지 유효한 계획(두 번째 범죄만 선택 / 두 범죄 모두 선택)이 정확히 계산되었음을 보여줍니다.