JArchive 프로그래밍 일기

문제

링크와 스타트 백준 15661번

리뷰

14889번 스타트와 링크 문제와 비슷했다.

스타트와 링크는 두 팀이 반드시 N/2 명씩 나뉘어야 했다.

이 문제는 두 팀이 1명 이상이면 된다는 조건이다. 하지만 팀 인원수가 1명이면, 능력치 계산을 못한다.

그래서 S팀이 2명일 때, S팀이 3명일 때, .... S팀이 N-2 명일 때의 경우를 모두 검사했다. DFS로 탐색했다.

    for(int i = 2; i < N-1; i++){  // 2명 부터 n-2명 까지의 범위 전부 검사 
        divideTeam(0, 0, i); 
    }

스타트와 링크 문제 풀이 포스팅

맞은 코드

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

int N;
int answer = 2e9;
bool check[21];
int S[21][21]; 

void countPower(){ // 팀별 능력치 비교  

    vector<int> Steam, Lteam; 
    int Spower=0, Lpower=0; 

    for(int i = 0; i < N; i++){  // 1. vector에 팀별 멤버번호 나눠담기 
        if(!check[i]) {
            Steam.push_back(i);
        }
        else Lteam.push_back(i);
    }    

    for(int i = 0; i < Steam.size(); i++){ // 2. 팀별 능력치 계산  
         for(int j = i+1; j < Steam.size(); j++){
             Spower = Spower + ( S[ Steam[i] ][ Steam[j] ] ) + ( S[ Steam[j] ][ Steam[i] ] );
        }
    }

    for(int i = 0; i < Lteam.size(); i++){  // Steam과 Lteam은 인원수가 다를 수 있다 
         for(int j = i+1; j < Lteam.size(); j++){
            Lpower = Lpower + ( S[ Lteam[i] ][ Lteam[j] ] ) + ( S[ Lteam[j] ][ Lteam[i] ] );
        }
    }

    // 3. 최소값 갱신 
    answer = min(abs(Spower-Lpower),  answer);

    return;
}

void divideTeam(int idx, int cnt, int target){ // N명중에 target 명 고르기  

    if(cnt == target) { // 팀 선택 완료 
        countPower();
        return;
    }

    for(int i = idx; i < N; i++){ // DFS로 완전탐색 

        if(check[i]) continue;

        check[i] = true;
        divideTeam(i+1, cnt+1, target);
        check[i] = false;
    }

}


int main(void){

     cin >> N;

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

    for(int i = 2; i < N-1; i++){ // 2명 부터 n-2명 까지의 범위 전부 검사 
        divideTeam(0, 0, i); 
    }

    cout << answer;

    return 0;
}