14889: 스타트와 링크

문제

• https://www.acmicpc.net/problem/14889
• 삼성 SW역량테스트 기출 문제

중요했던 내용

개인적으로 해맸던 2가지가 가장 중요했던거 같은데,

• 점수 산출 방법
• 조합/순열[무엇을 선택해야되는가?]

점수 산출 방법

문제에서 점수 산출 방법을 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다 라고 명시하고 있다.

즉, 팀이 2명인 경우[i/j]
s[i][j] + s[j][i] 가 되는 것이고

팀이 3명인 경우[i/j/k]
s[i][j] + s[i][k] + s[j][i] + s[j][k] + s[k][i] + s[k][j] 가 성립된다.

일반화 하자면 팀이 n명인 경우, 계산을 총 n^2 - n번 진행해야지 정확하다.

조합 / 순열

어쨌든 n명이 주어졌을 때, 2/n을 해서 팀을 뽑아야 되는데, 가장 중요한 점은 뽑는 순서는 중요치 않다~! 입니다. 즉, 조합을 선택해야지 저처럼 고생 안합니다.[저처럼 무작정 순열로 했다가 시간초과를...]

즉, 총 4명일 때, 팀원이 1/2/3/4 이렇게 있을 때, 1-2가 같이 있는 팀과 2-1이 같이 있는 팀의 점수는 동일합니다. 순열을 통해 불필요한 계산을 진행할 필요는 없습니다!

알고리즘[순서]

• 입력 전처리
  • 입력 받고, 2차원 배열 생성
• 각 팀을 생성
  • 팀은 재귀 형식으로 생성합니다.
  • 한 팀이 정해지면 Vector의 대칭 차집합 연산을 통해 나머지 팀을 결정하고
  • 각 팀의 점수를 계산합니다.
  • 각 팀의 점수를 뺀 것에 절댓값을 취해주고, 최솟값을 전역변수에 업데이트 합니다.

코드

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<vector<int>> reference;

vector<int> num;

int min_value = INT_MAX;

int calculate_pairs(vector<int>& array) {
    int sum = 0;
    for (int i = 0; i < array.size(); i++) {
        for (int j = 0; j < array.size(); j++) {
            if (j == i) continue;
            sum += reference[array[i]-1][array[j]-1];
        }
    }

    return sum;
}

void dfs_test(int start, vector<int> tmp, int depth, int limit, int n) {
    if (depth == limit) {
        // Second Array?
        vector<int> tmp_what(n*2);
        auto iter = set_symmetric_difference(num.begin(), num.end(), tmp.begin(), tmp.end(), tmp_what.begin());
        tmp_what.resize(iter - tmp_what.begin());


        min_value = min(min_value, abs(calculate_pairs(tmp) - calculate_pairs(tmp_what)));
        return;
    }

    for (int i = start; i <= n; i++) {
        vector<int> tmp_two = tmp; tmp_two.push_back(i);
        dfs_test(i+1, tmp_two, depth+1, limit, n);
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    int per_team = n / 2;
    vector<int> tmp;
    for (int i = 0; i < n; i++) {
        num.push_back(i+1);
    }

    reference.resize(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> reference[i][j];
        }
    }

    dfs_test(1, tmp, 0, per_team, n);

    cout << min_value << endl;
    return 0;
}