[백준][C++] 3980번: 선발 명단 <181>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

3980번: 선발 명단

생각의 흐름

맨 처음 나는 next_permutation을 통해 11명의 순열을 구한후, 그 배열이 0값을 포함하고 있지 않다면 결과를 도출하는 풀이로 풀었다.

하지만 시간초과가 발생하여 버렸다.

아마 순열을 구하는 과정에서 아예 답을 구할 수 있는데, 순열을 구한후, 다시 한번 순회를 돌기 때문 아닐까 싶다?

 

따라서 직접 순열을 구해 주었다.

for(int i = 0; i < MAX; i++){
    if(!visited[i] && MAP[index][i] != 0){
        visited[i] = true;
        go(index+1, sum + MAP[index][i]);
        visited[i] = false;
    }
}

0번 포지션 부터 10번 포지션 까지 반복하게 된다.

각 index번 째 사람이 i번째 포지션에 배당될 경우 받은 점수는 MAP[index][i]에 해당된다.

 

index번째 사람의 점수를 확인하기 위해 0~10 까지의 점수를 확인 해 본 후, 사용하지 않은 포지션 이면서 값이 0이 아니면 해당 값을 사용해 본다.

다음 사람에게 넘길때 go(index+1, ...)으로 넘어가게 된다.

 

처음 호출은 go(0, 0)으로 호출한다.

0번째 사람부터 포지션을 찾아줄것 이며, 이때 시작 점수는 0점 부터 시작한다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 11

int C;
int res;
int MAP[MAX][MAX];
bool visited[MAX];

void go(int index, int sum){
    if(index == MAX){
        if(res < sum) res = sum;
        return;
    }

    for(int i = 0; i < MAX; i++){
        if(!visited[i] && MAP[index][i] != 0){
            visited[i] = true;
            go(index+1, sum + MAP[index][i]);
            visited[i] = false;
        }
    }
}

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

    vector<int> vec;
    for(int i = 0; i < 11; i++){
        vec.push_back(i);
    }

    cin >> C;
    while(C--){
        for(int i = 0; i < 11; i++){
            for(int j = 0; j < 11; j++){
                cin >> MAP[i][j];
            }
        }
        memset(visited, false, sizeof(visited));
        res = 0;
        go(0, 0);
        cout << res << "\n";
    }
    
    return 0;
}