[백준] 3980 - 선발 명단

1. 문제 이해

각 테스트케이스마다 11번씩 11개의 숫자가 주어진다. 즉, 11X11개의 숫자가 주어진다.

각 숫자가 의미하는 것은 포지션에 적합한 정도를 의미한다.

각 포지션은 0 ~ 10으로 숫자로 나타낼 수 있다.

이 때 모든 포지션에 선수를 배치했을 때 최대 적합도를 찾는 문제이다. ( 정답은 항상 존재 )

---

 

2. 문제 풀이

숫자가 11개로 적으므로 브루트포스로 충분히 풀 수 있다. 포지션을 기준으로, 선수의 적합도를 더해나가면 된다. 이 때 기준은 포지션이 아니라 선수가 될 수 있다. 11명 전부 선택해야 하기 때문이다.

브루트포스는 재귀로 풀어나간다. 포지션별로 1명만 선택해야 하므로 어떤 포지션이 선택되었는지 알 수 있는 배열이 필요하다,

bool position[11]; // true이면 선택되었다는 의미이다.

 

그리고 적합도가 0이상인 선수만 선택될 수 있으므로 선택 조건은 아래와 같아진다.

!position[포지션 번호] && s[선수id][포지션 번호] > 0

재귀 호출이 끝나는 기저사례는 모든 포지션에 선수가 선택되었을 때이다. 즉, 재귀 함수가 12번째 호출될 떄이다. 그 떄 현재까지의 적합도의 합을 정답과 비교해서 클 경우 정답에 저장한다.

# 호출 카운트는 0부터 시작한다.
if(호출 카운트 == 11) {
    정답 = max(정답, 현재까지의 적합도의 합);
    # 종료
}

 

---

3. 문제 코드

#include <iostream>
#include <cstring>
using namespace std;
int s[11][11];
bool position[11];
int ans = -1;
void solve(int player, int fit_sum) {
    if(player == 11) {
        ans = max(ans, fit_sum);
        return ;
    }

    for(int i=0; i<11; i++) {
        if(!position[i] && s[player][i] > 0) {
            position[i] = 1;
            solve(player+1, fit_sum + s[player][i]);
            position[i] = 0;
        }
    }
}

void init() {
    ans = -1;
    memset(position, 0, sizeof(position));
}


int main() {
    int c; cin >> c;
    while(c--) {
        init();
        for(int i=0; i<11; i++) {
            for(int j=0; j<11; j++) {
                cin >> s[i][j];
            }
        }
        solve(0, 0);
        cout << ans << "\n";
    }
}