[Algorithm] 백준 14889번 스타트와 링크

백준 14889번 스타트와 링크

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

팀원들 한명씩 돌면서 start팀으로 사용할까 말까를 구현해서 코딩하면 됨.

확인은 안해봤지만, 아래와 같은 경우는 똑같은 계산을 2번 하게 되는 문제가 생길 수 있음

ex) 4명의 사원(1~4)

    start팀(1,2)   link팀 (3,4)

    start팀(3,4)   link팀 (1,2)

그래서 미리 전체 조합수(totalCase)를 계산해서 그 절반까지만 계산을 하도록 하였음. (Line 41)

어차피 순차적으로 앞에서부터 한명씩 고르기 때문에 총 진행에 절반만큼만 하면 중복되는 경우는 하지 않기 때문입니다.

참 쉽쥬?

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
 
#define ll long long int
 
using namespace std;
int N;
int synergy[21][21];
bool stVisit[21];
ll answer = 1e10;
ll totalCase = 0;
void calSynergy()
{
    int startSynergy = 0;
    int linkSynergy = 0;
    for (int i = 0; i < N; i++) {
        if (stVisit[i]) {
            for (int j = i + 1; j < N; j++) {
                if (stVisit[j]) {
                    startSynergy += (synergy[i][j] + synergy[j][i]);
                }
            }
        }
        else {
            for (int j = i + 1; j < N; j++) {
                if (!stVisit[j]) {
                    linkSynergy += (synergy[i][j] + synergy[j][i]);
                }
            }
        }
    }
    if (answer > abs(startSynergy - linkSynergy)) {
        answer = abs(startSynergy - linkSynergy);
    }
}
int choiceCase = 0;
void choiceStartTeam(int pos, int stCnt) {
    if (pos > N || choiceCase == totalCase) return;
    if (stCnt == N / 2) {
        calSynergy();
        choiceCase++;
        return;
    }
 
    stVisit[pos] = true;
    choiceStartTeam(pos + 1, stCnt + 1);
    stVisit[pos] = false;
    choiceStartTeam(pos + 1, stCnt);
}
void calTotalCase() {
    totalCase = 1;
    for (int i = N; i >= 2; i--) {
        totalCase *= i;
    }
    for (int i = N / 2; i >= 2; i--) {
        totalCase /= pow(i, 2);
    }
 
}
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> synergy[i][j];
        }
    }
    calTotalCase();
    choiceStartTeam(0, 0);
    cout << answer;
    return 0;
}