백준 15661 링크와 스타트

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

#include <iostream>
#include <vector>
#include <cmath>

#define INF 987654321

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<vector<int>> arr(n, vector<int>(n, 0));

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

    int ans = INF;

    //스타트팀 1명 링크팀 3명=스타트팀 3명 링크팀 1명, 각 팀당 적어도 한 명 있어야 한다는 점 고려
    for (int bit = 1; bit < pow(2, n) - 1; bit++) {
        int s = 0;          //bit=1
        int l = 0;          //bit=0

        vector<int> str;
        vector<int> lin;

        for (int i = 0; i < n; i++) {
            if (bit & (int)pow(2, i)) {
                str.push_back(i);
            } else {
                lin.push_back(i);
            }
        }

        if (str.size() > 1) {
            for (int i = 0; i < str.size(); i++) {
                for (int j = i + 1; j < str.size(); j++) {
                    s += arr[str[i]][str[j]] + arr[str[j]][str[i]];
                }
            }

        }

        if (lin.size() > 1) {
            for (int i = 0; i < lin.size(); i++) {
                for (int j = i + 1; j < lin.size(); j++) {
                    l += arr[lin[i]][lin[j]] + arr[lin[j]][lin[i]];
                }
            }

        }

        ans = min(ans, abs(s - l));

    }

    cout << ans;

    return 0;
}

1. 문제

축구에 참여할 총 인원 수와 능력치가 주어진다. 능력치는 두 사람이 같은 팀에 속해있을 때 해당 위치의 능력치의 합으로 계산한다.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

두 팀의 능력치 차이를 최소로 하고자 할 때, 그 차이를 구하는 문제이다.

2. 풀이

총 인원이 20명이고, 제한시간이 2초이므로 브루트포스로 해결할 수 있다.

 for (int bit = 1; bit < pow(2, n) - 1; bit++)

n명의 사람을 두 팀으로 나누어야 하므로 범위를 다음과 같이 설정한다. 팀의 인원이 달라도 되지만 각 팀에 적어도 한 명존재해야 하므로 111...1(n개)는 세지 않는다.

        int s = 0;          //bit=1
        int l = 0;          //bit=0

        vector<int> str;
        vector<int> lin;

        for (int i = 0; i < n; i++) {
            if (bit & (int)pow(2, i)) {
                str.push_back(i);
            } else {
                lin.push_back(i);
            }
        }

스타트 팀과 링크 팀의 능력치와 각 사람을 저장할 벡터를 선언하고, 비트 값에 따라 해당 인원을 배치한다.

       if (str.size() > 1) {
            for (int i = 0; i < str.size(); i++) {
                for (int j = i + 1; j < str.size(); j++) {
                    s += arr[str[i]][str[j]] + arr[str[j]][str[i]];
                }
            }

        }

        if (lin.size() > 1) {
            for (int i = 0; i < lin.size(); i++) {
                for (int j = i + 1; j < lin.size(); j++) {
                    l += arr[lin[i]][lin[j]] + arr[lin[j]][lin[i]];
                }
            }
            
        ans=min(ans, abs(s-l));

 팀원의 수가 두 명 이상일 경우, 적어도 하나의 능력치를 더할 수 있다. 팀원이 한명일 경우 능력치를 계산할 수 없으므로 고려하지 않는다. 이전에 넣은 각 팀원에 대해 능력치를 계산하여 각 팀에 더한다.

 이후 계산한 두 팀의 능력치 차이를 ans에 최솟값으로 갱신한다. 연산이 끝난 후 ans를 출력하면 답을 구할 수 있다.