[알고리즘] 스타트와 링크

1. 포인트

• 조건대로 구현을 할 수 있는가?
• 그동안 너무 어렵게 생각한 것은 아닌가 고민이 된다.
• 조합을 구현한뒤 나누어서 값을 더하는 로직
• dfs 에서 순열, 중복 순열, 조합, 중복 조합 정도는 알고 있으면 상당히, 아주 상당히 좋을 것 같다.
• 전역변수를 잘 사용하는 것도 좋다

c++/cpp

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

using namespace std;
int map[21][21];

int main() {
    int n;
    cin >> n;

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

    vector<int> b(n);
    for (int i = 0; i < n / 2; i++) {
        b[i] = 1;
    }
    sort(b.begin(), b.end()); //permutation 은 항상 sort 가 되어 있어야 한다.
    int ans = 2147483647;
    do {
        vector<int> first, second;

        for (int i = 0; i < n; i++) {
            if (b[i] == 0) {
                first.push_back(i);
            } else {
                second.push_back(i);
            }
        }

        int one = 0;
        int two = 0;

        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (i == j) continue;
                one += map[first[i]][first[j]];
                two += map[second[i]][second[j]];
            }
        }

        int diff = one - two;
        if (diff < 0) diff = -diff;
        ans = min(ans, diff);
    } while (next_permutation(b.begin(), b.end()));

    cout << ans << '\n';
    return 0;
}

python

import sys

sys.stdin = open('input.txt')

n = int(input())

data = [list(map(int, input().split())) for _ in range(n)]

sel = []

result = 987654321


def go(index: int):
    global result
    if len(sel) == n // 2: # 조합을 선택하는 방법
        unsel = [ele for ele in range(n) if ele not in sel]
        result_a = 0
        result_b = 0

        for i in range(n):
            for j in range(n):
                # 어차피 i==j 는 0
                # i 하고 j 가 같은 팀이면
                if i in sel and j in sel:
                    result_a += data[i][j]
                if i in unsel and j in unsel:
                    result_b += data[i][j]

        # 값 계산
        result = min(result, abs(result_a - result_b))  # 최솟값을 저장

        return

    if index >= n: # 인덱스 범위를 넘어가면 종료
        return

    sel.append(index)
    go(index + 1)
    sel.pop()

    go(index + 1)


go(0)
print(result)