3980번 - 선발명단

해결방법

bitmask dp로 해결하였다.dp를 2차원 배열로 (position, state)를 담을 수 있게 정의하였다.

 int dp[11][1 << 11]
 int s[11][11] // s[i][j] i는 j포지션의 능력치

(state >> t) % 2 == 0은 t라는 포지션이 0일 경우 아직 배정이 안됬으므로 배정을 해야한다는 조건이다. 더해서 포지션의 능력치가 0이 되면 안되기 때문에 s[p][t] != 0아닌 것도 포함해줘야 한다.
sub를 둔 이유는 조건에 맞는 포지션이 없을 경우 -1를 리턴하는데, 이 경우는 포지션을 모두 배정하지 못한 경우의 수므로 제외시켜줘야 한다.

 if ((state >> t) % 2 == 0 && s[p][t] != 0) {
    int sub = solution(p + 1, state | 1 << t);
    if(sub != -1)
        ret = max(ret, sub + s[p][t]);
 }

전체코드

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[11][1 << 11], s[11][11], TC;
int solution(int p, int state) {
    if (p == 11) return 0;
    int& ret = dp[p][state];
    if (ret != -1) return ret;
    for (int t = 0; t < 11; ++t)
        if ((state >> t) % 2 == 0 && s[p][t] != 0) {
            int sub = solution(p + 1, state | 1 << t);
            if(sub != -1)
                ret = max(ret, sub + s[p][t]);
        }
    return ret;
}
int main() {
    cin >> TC;
    while (TC--) {
        memset(dp, -1, sizeof(dp));
        for (int y = 0; y < 11; ++y)
            for (int x = 0; x < 11; ++x)
                cin >> s[y][x];
        cout << solution(0, 0) << endl;
    }
    return 0;
}