[ BOJ 백준 3980번 - 선발 명단 ] 해설 및 코드

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

 

목적

11명의 선수의 포지션 별 능력치가 주어지고, 각 포지션에 배치했을 때 능력치의 최대합을 구하자.

 

접근법

1. DFS 완전탐색으로 접근하자.

2. 포지션에 능력치가 0인 선수는 배치 불가하니 이에 대한 처리를 해준다.

 

#include<iostream>
#include<cmath>
#include<cstring>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
const int mn=-1100;
int s[11][11],cache[1<<11];
 
int maxSum(int i,int bitset){
    if(i==11)return 0;
    
    int& ref=cache[bitset];
    if(ref!=-1)return ref;
    
    ref=mn;
    f(j,0,11)if(!((1<<j)&bitset)&&s[j][i])ref=max(ref,s[j][i]+maxSum(i+1,bitset|(1<<j)));
    return ref;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int t; cin >> t;
    while (t--) {
        f(i, 0, 11)f(j, 0, 11)cin >> s[i][j];
        memset(cache,-1,sizeof(cache));
        cout << maxSum(0, 0) << '\n';
    }
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.