C++로 풀기: n명의 사람이 서로 다른 모자를 쓰는 경우의 수

n명의 사람과 1부터 40까지 번호가 매겨진 40가지 종류의 모자가 있다고 가정해 보겠습니다. 2차원 배열 hats가 주어지며, hats[i]는 i번째 사람이 선호하는 모자 번호들의 목록을 의미합니다. 우리가 구해야 할 것은 n명의 사람이 모두 서로 겹치지 않는 모자를 쓰도록 배정하는 방법의 수입니다. 답이 매우 커질 수 있으므로, 최종 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다.

예를 들어 입력이 [[4,6,2],[4,6]]라고 한다면 출력은 4가 됩니다. 첫 번째 사람은 4, 6, 2번 모자 중 하나를, 두 번째 사람은 4, 6번 모자 중 하나를 쓸 수 있는데, 서로 다른 모자를 쓰는 조합은 [4,6], [6,4], [2,4], [2,6]으로 총 4가지이기 때문입니다.

문제 해결 접근 방식

이 문제는 비트마스크(bitmask) 동적 계획법(DP)과 메모이제이션(memoization)을 결합하면 효율적으로 풀 수 있습니다. 모자 번호를 차례대로 순회하면서, 현재 모자를 어떤 사람에게 씌우거나 아무에게도 씌우지 않고 건너뛰는 두 가지 선택지를 재귀적으로 탐색합니다. 이때 비트마스크를 사용해 이미 모자를 배정받은 사람들을 추적함으로써 동일한 상태에 대한 중복 계산을 방지할 수 있습니다.

알고리즘 단계

모듈러 값 m을 10^9 + 7로 설정합니다.
크기가 55 × 2^11인 2차원 배열 dp를 정의하고, 2차원 벡터 v를 준비합니다.
add(a, b) 함수를 정의합니다. 이 함수는 ((a mod m) + (b mod m)) mod m을 반환합니다.
solve(idx, mask) 함수를 정의합니다.
- mask가 req와 같으면 1을 반환합니다. (모든 사람에게 모자가 배정된 완성 상태)
- idx가 42이면 0을 반환합니다. (더 이상 고려할 모자가 없음)
- dp[idx][mask]가 -1이 아니라면 이미 계산된 값이므로 그대로 반환합니다.
- 먼저 현재 모자를 아무에게도 씌우지 않고 건너뛰는 경우를 더합니다. ret := add(ret, solve(idx + 1, mask))
- v[idx]에 포함된 모든 사람 i에 대해, mask의 i번째 비트가 0이라면(아직 모자를 받지 못한 사람이라면) 그 사람에게 현재 모자를 씌우는 경우를 더합니다. ret := add(ret, solve(idx + 1, mask OR 2^i))
- 계산된 ret을 dp[idx][mask]에 저장한 후 반환합니다.
메인 함수에서는 다음을 수행합니다.
- dp 배열 전체를 -1로 초기화합니다.
- n := x의 크기를 구합니다.
- v의 크기를 50개 요소를 담을 수 있도록 조정합니다.
- i를 0부터 x의 크기 미만까지 순회하면서, x[i]에 포함된 모든 모자 번호 j에 대해 v[j]의 끝에 i를 추가합니다. 즉, j번 모자를 좋아하는 사람들의 목록을 만드는 것입니다.
- req := (2^n) − 1로 설정합니다. (모든 사람에게 모자가 배정되었음을 나타내는 마스크)
- ret := solve(0, 0)을 호출하고 그 결과를 반환합니다.

다음 구현 예시를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
int m = 1e9 + 7;
int dp[55][1 << 11];
class Solution {
    public:
    vector<vector<int> > v;
    int req ;
    int add(lli a, lli b){
        return ((a % m) + (b % m)) % m;
    }
    int solve(int idx, int mask){
        if (mask == req)
        return 1;
        if (idx == 42)
        return 0;
        if (dp[idx][mask] != -1) {
            return dp[idx][mask];
        }
        int ret = add(ret, solve(idx + 1, mask));
        for (int i : v[idx]) {
            if (!((mask >> i) & 1)) {
                ret = add(ret, solve(idx + 1, mask | (1 << i)));
            }
        }
        return dp[idx][mask] = ret;
    }
    int numberWays(vector<vector<int>>& x){
        memset(dp, -1, sizeof dp);
        int n = x.size();
        v.resize(50);
        for (int i = 0; i < x.size(); i++) {
            for (int j : x[i]) {
                v[j].push_back(i);
            }
        }
        req = (1 << n) - 1;
        int ret = solve(0, 0);
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{4,6,2},{4,6}};
    cout << (ob.numberWays(v));
}

입력

{{4,6,2},{4,6}}