JArchive 프로그래밍 일기

문제

스타트와 링크 백준 14889번

리뷰

N개 중에 중복없이 N/2 개를 고른다. N과 M 문제를 다시 풀어보고 이 문제를 풀었다.

1 2 3 4 번 사람이 있으면, (총 인원 4명)

1 2 이렇게 두 명만 A팀으로 고르면 3 4 는 자동으로 B팀으로 정해진다.

그리고 1 2 를 고르면 다음에는 1 3 을 선택해야 한다.

그런데 두 명을 고르는데, 3번 사람 부터 고를 때는. 3 1 이 아니라 3 4 를 골라야 한다.

3번 사람을 고른 상태에서는, 4번 사람만 고를 수 있다.

앞서 고른 수보다 큰 수를 골라야 1 3, 3 1 처럼 중복 없이 고를 수 있다. N과 M 2에서 풀었던 코드의 구조를 따왔다. (조합)

N/2 명을 고르면 팀이 나눠진 것이다.

그 다음에는 벡터 A, B 에 숫자를 넣어두고, power 배열의 인덱스를 이용해서 능력치의 합을 구한다.

abs 함수로 절대값을 구해 처리했고 min 함수로 차이의 최소값를 계산했다.

코드

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

int N; 
int ch[21]; // 사람 선택 할 때 중복 방지  
int map[21][21];
int mindiff = 2e9;

void go(int index, int cnt){

    if(cnt == N/2){ //  N/2만큼 골랐다면, 팀 나눈다.  

         vector<int> S, L;
         int Ssum = 0, Lsum = 0;

         for(int i = 0; i <N; i++){ // 팀 나눠서 벡터에 담는다.  
             if(ch[i]) S.push_back(i);
             else L.push_back(i);
        }

        for(int i = 0; i < S.size(); i++){ // 팀별로 능력치 합  
            for(int j = i+1; j < S.size(); j++){
                Ssum += (map[S[i]][S[j]] + map[S[j]][S[i]]);
                Lsum += (map[L[i]][L[j]] + map[L[j]][L[i]]);
            }
        }

        mindiff = min(mindiff, abs(Ssum-Lsum) ) ; // 차이값 갱신 
        return;
    }

    for(int i = index; i < N; i++){ // index 자리의 사람 선택 
        if(ch[i]) continue; // 이미 선택한 사람이면 지나감 

        ch[i] = 1; // 선택 
        go(i+1, cnt+1); // 다음 사람 선택하러 재귀호출 
        ch[i] = 0; // 선택 안 함.
    }

}

int main(void){

    cin >> N;

     for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
             scanf("%d", &map[i][j]);
        }
    }

     go(0, 0);

     cout << mindiff;

    return 0;
}