[BOJ/백준][Gold4] 3980 : 선발 명단 (C++)

https://www.acmicpc.net/problem/3980

3980번: 선발 명단

 

 

[난이도] Gold4
[유형] DP,Bitmask,완전탐색

[풀이]
next_permutation으로 푸니까 TLE로 틀려서 Bitmask DP로 풀었다.
선수 11명, 포지션 11개밖에 안되므로 DP[11][1<11] 배열로
11x2^11 O(22528) 안에 해결이 가능하다.

next_permutation이 아닌 재귀를 활용한 완전탐색으로도 0인 경우에 가지치기를 해주면
시간내에 해결이 가능하다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,a[11][11],dp[11][1<<11],inf=-9e8;
int sol(int n,int msk){
    if(n==11) return 0;
    int& ret = dp[n][msk];
    if(ret!=-1) return ret;
    ret = inf;
    for(int i=0;i<11;i++){
        if(((1<<i)&msk)==0 && a[i][n]){
            ret = max(ret,sol(n+1,msk|(1<<i))+a[i][n]);
        }
    }
    return ret;
}
int main(){ 
    scanf("%d",&tc);
    while(tc--){
        for(int i=0;i<11;i++)
            for(int j=0;j<11;j++) scanf("%d",&a[i][j]);       
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(0,0));
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/3980.cpp