baekjoon/14889.cpp at main · simsgood2/baekjoon · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;

int val[21][21];
bool pick[21]; // 뽑았는지 확인
int n;
int mini = 987654321;
void summ()
{
    int ret1 = 0, ret2 = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (pick[i] && pick[j])
            {
                ret1 += val[i][j];
            }
            else if ((!pick[i]) && (!pick[j]))
            {
                ret2 += val[i][j];
            }
        }
    }
    mini = min(mini, abs(ret2 - ret1));
}

void makeTeam(int m, int index)
{ // 몇명뽑았는지, 위치

    if (m == n / 2)
    {
        summ();
        return;
    }
    for (int i = index; i <= n; i++)
    {
        pick[i] = 1;
        makeTeam(m + 1, i + 1);
        pick[i] = 0;
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> val[i][j];
        }
    }

    makeTeam(0, 1);
    cout << mini << "\n";
    return 0;
}