[백준] 15661 링크와 스타트

문제의 출처는 아래와 같다.

 

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

 

이 문제는 삼성 역량테스트 기출문제인 '스타트와 링크' 의 상위호환 버전으로 문제가 조금 변형된 문제이다.

원래 문제에서는 팀을 두 그룹으로 나눌 때, 팀의 인원이 같은 즉, N/2 명으로 동일한 상태를 요구했다.

 

이 문제는 팀을 두 그룹으로 나눌 때, 팀의 인원이 다를 수 있다. 즉 N이 4일때 (1) , (2,3,4) 와 같이 팀의 인원이 다른 상태를 생각해야 하는 문제이다. 

그래서 필자는 그룹을 나누기 위해 부분집합을 사용하였다. 부분집합을 구하면서 바로 연산을 해도 되지만 필자는 N의 부분집합을 모두 구한 상태에서 조건에 맞지 않는 부분과 이미 동일한 부분집합의 내용일때 그 경우를 바로 리턴하였다. 규칙상 N이 4일때 총 16개의 부분집합이 있는데 우리는 이중 공집합을 제외한 7개 부분만 사용하면 된다.

 

경우를 모두 구했으면 문제에서 요구하는대로 구현하면 된다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
int n, arr[21][21], visit[21],dup,ans=987654321;
 
void dfs(int a, int b) {
    //if (a > n / 2) return;
    //printf("%d\n", b);
    if (a == n+1) {
        dup++;
        if (dup > (pow(2.0, n) / 2)-1) return;
        int val1 = 0, val2 = 0, chk1 = 0, chk2 = 0;
        vector<int> t1, t2;
        for (int i = 1; i <= n; i++) {
            if (visit[i] == 1) t1.push_back(i);
            else t2.push_back(i);
        }
        if (t1.empty() || t2.empty()) return;
        //printf("dup: %d\n", dup);
        //for (auto &i : t1) cout << i << "  ";
        //printf("\n");
        //for (auto &i : t2) cout << i << "  ";
        //printf("\n\n");
        for (int i = 0; i < t1.size(); i++) {
            for (int j = 0; j < t1.size(); j++) {
                chk1 = chk1 + arr[t1[i]][t1[j]];
            }
        }
        for (int i = 0; i < t2.size(); i++) {
            for (int j = 0; j < t2.size(); j++) {
                chk2 = chk2 + arr[t2[i]][t2[j]];
            }
        }
        //printf("%d %d", chk1, chk2);
        ans = min(ans,abs(chk1 - chk2));
        //printf("\n");
        return;
    }
    visit[a] = 1;
    dfs(a + 1, b);
    visit[a] = 0;
    dfs(a + 1, b);
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    dfs(1, 0);
    printf("%d", ans);
    return 0;
}