[백준/백트래킹/C++] 15661번 링크와 스타트 *

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

15661번: 링크와 스타트

계속 시간초과가 떠서 찾아봤는데 팀을 구성할 때

스타트팀 : 1,2 링크팀 : 3,4 일때와 스타트팀 : 3,4 링크팀 : 1,2 일때 두번 구해져서 그런 것이었다

void makeTeam(int tot){
    if(tot == n){
        compare();
        return;
    }

    isStartTeam[tot] = true; // tot번의 선수가 start팀에 있는 경우
    makeTeam(tot+1);
    isStartTeam[tot] = false; // tot번의 선수가 start팀에 없는 경우
    makeTeam(tot+1);
}

makeTeam() 함수는 그 조합을 구하는 함수이고  tot 변수는 팀 인원을 뜻하기도 하고 tot 번째 선수를 말하기도 한다.

1. tot 번째 선수가 start 팀에 있는 경우

2. tot 번째 선수가 start 팀에 없는 경우 에도 n번째까지 makeTeam 함수를 돌려서 최소값을 구한다

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n;
int s[21][21];
bool isStartTeam[21]; // start팀 : true
int result = 2e9;

void compare(){ // 능력치 비교
    int pStart = 0, pLink = 0;

    for(int i=1; i<=n-1;i++){
        for(int j=i+1; j<=n; j++){

            if(isStartTeam[i] && isStartTeam[j])
                pStart += s[i][j] + s[j][i];
            else if(!isStartTeam[i] && !isStartTeam[j])
                pLink += s[i][j] + s[j][i];
        }
    }

    result = min(result, abs(pStart - pLink));
}

void makeTeam(int tot){
    if(tot == n){
        compare();
        return;
    }

    isStartTeam[tot] = true; // tot번의 선수가 start팀에 있는 경우
    makeTeam(tot+1);
    isStartTeam[tot] = false; // tot번의 선수가 start팀에 없는 경우
    makeTeam(tot+1);
}

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

    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> s[i][j];
        }
    }

    makeTeam(0);

    cout << result;

    return 0;
}

 

관련 문제

https://develop-me-z.tistory.com/158

[백준/백트래킹/C++] 14889번 스타트와 링크 (삼성 SW 역량 테스트 기출)