BOJ 14889 - 스타트와 링크(C++)

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

14889번: 스타트와 링크

 

풀이

1. 스타팀에 누가 포함될지 N/2명을 뽑는 경우의 수에 대해 탐색

  - bool 자료형의 1차원 배열 visit을 이용하여 스타트 팀에 포함되었는지 여부를 확인

    - 배열의 값이 true면 스타트 팀, false면 링크 팀

2. 스타트 팀, 링크 팀에 대해 각각 점수 계산

  - 2중 for문을 이용하여 i와 j가 같은 팀일때의 해당 팀의 점수를 더함

  - visit[i] && visit[j] 이면 스타트 팀, !visit[i] && !visit[j] 이면 링크 팀

탐색 범위를 좁히는 방법 흰색 칸에 대해서만 탐색 (j = i+1 부터)  i와 j가 같은 팀이라면 00_score += arr[i][j] + arr[j][i]으로 갱신 (회색 칸에 대해 탐색 할 필요 X)

3. 각 팀의 점수 차이의 최소를 갱신

4. 1로 돌아가 다음 경우의 수에 대해 탐색

 

#include <iostream>

using namespace std;

int N;
int arr[21][21];
bool visit[21];
int MIN = 987654321;

void check_performance() {
    int start_score = 0;
    int link_score = 0;
    int res;
    for (int i = 1; i <= N; i++) {
        for (int j = i+1; j <= N; j++) {
        	// i와 j가 같은 팀일 때만 점수 계산
            if (visit[i] && visit[j]){
                start_score += arr[i][j];
                start_score += arr[j][i];
            }
            else if (!visit[i] && !visit[j]){
                link_score += arr[i][j];
                link_score += arr[j][i];
            }

        }
    }   
    res = abs(start_score - link_score);
    MIN = res < MIN ? res : MIN;
}

void select(int cnt, int idx) {
    if (cnt == N / 2) {
        check_performance();
        return;
    }
    
    for (int i = idx; i <= N; i++) {
        // visit을 이용하여 팀의 구성원을 저장 -> 점수 계산(check_performance())에서 사용
        // true -> 스타트 팀, false -> 링크 팀
        visit[i] = true;
        select(cnt + 1, i + 1);
        //다음 탐색을 위하여 visit을 처음 상태로 복구
        visit[i] = false;
    }
}

int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
        }
    }

    select(0, 1);
    cout << MIN;

    return 0;
}