[소프트웨어 익스퍼트 아카데미][SWEA][모의 SW 역량테스트][ C++][4012번] 요리사

dfs를 통해 풀 수 있던 문제 였습니다. 또한 문제를 잘 읽어 봐야 합니다.

문제의 설명에서는 N=4인경우만 있었지만

N이 8이나 10같은 4보다 큰 짝수일 경우 N/2만큼을 고르는 것이고

음식의 시너지는 예를들어 N=6이고 A음식에서 1,2,3번을 골랐다고 한다면

(1,2),(1,3)(2,3)을 모두 더하여 시너지를 구해야 합니다.

#include<iostream>
#include<deque>
using namespace std;
 
int N;
int ans;
int food[17][17];
int sum[3];
bool visited[17];
int A[9];
int B[9];
 
void init() {
    ans = 987654321;
    
}
 
void func() {
    int sum_A = 0; int sum_B = 0;
    for (int i = 1; i <N / 2; i++) {
        for (int j = i + 1; j <= N / 2; j++) {
            sum_A += food[A[i]][A[j]] + food[A[j]][A[i]];
            sum_B += food[B[i]][B[j]] + food[B[j]][B[i]];
        }
    }
    int ans_temp = abs(sum_A - sum_B);
    if (ans > ans_temp) ans = ans_temp;
}
 
void sel(int dep,int end,int start) {
    if (dep == end) {
        int a = 1; int b = 1;
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                A[a] = i;
                a++;
            }
            else {
                B[b] = i;
                b++;
            }
        }
        func();
        return;
    }
    for (int i = start; i <= N; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        start = i;
        sel(dep + 1, end,i);
        visited[i] = false;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    scanf("%d", &T);
    //cin >> T;
    for (int t = 1; t <= T; t++) {
        init();
        scanf("%d", &N);
        //cin >> N;
        for (int Y = 1; Y <= N; Y++) {
            for (int X = 1; X <= N; X++) {
                scanf("%d", &food[Y][X]);
                //cin >> food[Y][X];
            }
        }
        sel(0,N/2,1);
        printf("#%d %d\n", t, ans);
        //cout << "#" << t << " " << ans << endl;
    }
}