[백준] 3980번 선발 명단 C++

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

C++

#include<iostream>
#include<vector>
using namespace std;

int player[11][11];
bool visited[11];
int Max;

void search(int position, int maxx) {
    if(position==11) {
         Max = max(Max , maxx);
    }

    for(int i = 0; i < 11; i++) {
        if(!visited[i] && player[i][position] != 0) {
            visited[i] = true;
            search(position+1, maxx + player[i][position]);
            visited[i] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 11명의 선수가 각각의 포지션에서의 능력 0부터 100
    // 모든 선수의 포지션 정하는 프로그램, 각 선수는 능력치가 0인 포지션에 배치 못함
    // 모든 선수에게 적합한 포지션의 수는 최대 5개(능력치 0보다 크다)

    int test;
    cin >> test;

    while(test--) {
        Max = 0;
        for(int i = 0; i < 11; i++) {
            for(int j = 0; j < 11; j++) {
                cin >> player[i][j];
            }
        }
        search(0,0);
        cout << Max << "\n";
    }
}

문제풀이

• 각 포지션에 대해서 가장 높은 능력치를 가진 선수를 뽑아야한다. 문제를 보면서 백트래킹과 DFS 방법이 떠올랐다. 그래서 일단 11명 포지션에 대해 11명 선수들의 각 능력치를 입력받았다. 그리고 bool타입 visited를 통해 방문했는지를 판단하고 max함수를 사용해서 최댓값을 구했다.

Comment

• 백트래킹과 DFS문제를 처음 풀었을 때는 어떤식으로 접근하고 사용해야되는지 감이 잡히지 않았는데 여러 문제를 풀어보니까 점점 길이 보이는 것 같다. 확실히 알고리즘은 여러 문제를 많이 풀어봐야한다!