백준 15661. 링크와 스타트

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

15661번: 링크와 스타트

 

분명 이전에 푼 문제같은데 안풀어져 있어서 찾아봤더니 이전에 푼 문제는 14889.스타트와 링크였다.

이전에 푼 문제와 다른 점은 이전꺼는 모인 인원수가 무조건 짝수고 정학히 팀을 반으로 나누는 것이었고

이번 문제는 두 팀의 인원수는 서로 다를수 있다는 것.

 

1. 1명 부터 n-1명 까지 뽑는 조합을 dfs로 구한다.

  n=4라면 

  1명 뽑는 조합: {1}, {2}, {3}, {4}

  2명 뽑는 조합: {1,2}, {1,3}, {1,4} ... 

  3명 뽑는 조합: {1,2,3}, {1,2,4}... 

뽑히지 않은 수가 다른 팀이다.

 

2. 이렇게 팀이 정해졌으니, 이제 두 팀의 점수를 구하고 차를 구한다.

 

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

int n;
int ans = 999999999;
int S[21][21];

vector<int> member;
bool mark[21];

int CalculateTeamScore(vector<int> v)
{
    // 팀 점수 계산
    int teamScore = 0;
    for(int i = 0; i < v.size(); i++)
    {
        for(int j = 0; j < v.size(); j++)
        {
            // 자기자신과의 계산은 제외
            if(j == i) continue;
            teamScore += S[v[i]][v[j]];
        }
    }

    return teamScore;
}

void Calculate()
{
    vector<int> link, start;
    for(int i = 0; i < n; i++)
    {
        if(mark[i])
            link.push_back(member[i]);
        else
            start.push_back(member[i]);
    }

    int linkScore = CalculateTeamScore(link);
    int startScore = CalculateTeamScore(start);

    ans = min(ans, abs(linkScore - startScore));
}

// howMany명의 조합 뽑음
void dfs(int idx, int depth, int howMany)
{
    if(depth == howMany)
    {
        // 팀 뽑은 상태에서 팀의 점수 계산
        Calculate();

        return;
    }

    for(int i = idx; i < n; i++)
    {
        if(mark[i]) continue;
        mark[i] = true;

        dfs(i, depth+1, howMany);

        mark[i] = false;
    }
}

int main()
{
    // inputs
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> S[i][j];
        }
    }

    // 1,2,3,...,n
    for(int i = 1; i <= n; i++)
        member.push_back(i);

    for(int i = 1; i < n; i++)
    {
        dfs(0, 0, i);
    }

    cout << ans;
}