백준 3980 - 선발 명단

 

www.acmicpc.net/problem/3980

3980번: 선발 명단

11명의 선수를 배치했을 때 최대 능력치를 구하는 문제이다.

11명을 전부 배치할 수 있는 TC만 주어지며 반드시 11명을 배치해야 한다는 점을 주의하자.

 

 

11명을 반드시 배치해야 한다는 조건에 주목하여 비트마스크 DP, 탐색 등의 방법을 통해 능력치의 최댓값을 찾도록 한다.

단, 비트마스크 DP를 이용시 다음과 같은 케이스에 유의하도록 한다.

 

1
10 0 0 0 0 0 0 0 0 0 0
0 10 0 0 0 0 0 0 0 0 0
0 0 10 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1

 

이 TC의 답은 29가 되어야 하지만 DP를 수행하면서 3번째 행에서 10을 선택한 후 4번째 행을 선택하지 못할 때 문제가 발생한다. 해당 DP 테이블의 초기값을 0으로 설정하면 그대로 30이 리턴되면서 오답을 출력하게 된다.

이 소스에서는 계산하려는 테이블의 초기값에 충분히 작은 음수를 부여해 선수를 선택하지 못했을 경우 음수를 리턴하게 하여 dp 값 비교시 완성될 수 없는 배치가 선택되는 것을 방지하였다.

 

전체 코드 - 비트마스크 DP

#include <bits/stdc++.h>

using namespace std;

int stat[11][11];
int dp[1 << 11];

int memo(int idx, int cur_bit);

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int t; cin >> t;
    while (t--)
    {
        memset(dp, -1, sizeof dp);
        memset(stat, 0, sizeof stat);
        
        for (int i = 0; i < 11; ++i)
            for (int j = 0; j < 11; ++j)
                cin >> stat[i][j];
        
        cout << memo(0, 0) << '\n';
    }
}

int memo(int idx, int cur_bit)
{
    if (__builtin_popcount(cur_bit) == 11)
        return 0;
    
    int &ret = dp[cur_bit];
    
    if (ret != -1)
        return ret;
    
    ret = -1200;
    
    for (int i = 0; i < 11; ++i)
        if (stat[idx][i] && !(cur_bit & (1 << i)))
            ret = max(ret, stat[idx][i] + memo(idx + 1, cur_bit | (1 << i)));
    
    return ret;
}

 

ICPC Regional 문제들은 전체적인 로직뿐만 아니라 세세한 부분에서 신경을 써야 하는 것 같다.