4012. [모의 SW 역량테스트] 요리사

조합을 2번 구해줘야한다!!

한 재귀함수의 특정 조건이 만족하면 거기서 다른 함수의 재귀를 타면 된다!!

무슨소리냐하면,

1. A와B의 요리 개수를 N/2개씩 나누어 가져야하므로, 이때 재귀를.

2. N/2개씩 나누었으면, i와j의 시너지를 찾아야 하므로 재귀를 타면 된다.

#include <stdio.h>
#include <string.h>
 
 
int map[17][17];
int visit[17];
int IJ[2];
int N, MIN;
 
int abs(int a, int b)
{
    return a - b < 0? -1 * (a - b) : a - b;
}
 
int Sij(int cur, int n, int who)
{
    int total = 0;
    if (n == 2)
    {
        return map[IJ[0]][IJ[1]] + map[IJ[1]][IJ[0]];
    }
 
    for (int i = cur + 1; i <= N; i++)
    {
        if (who == 1 && visit[i] != 0 && IJ[n] == 0)
        {
            IJ[n] = i;
            total += Sij(i, n + 1, who);
            IJ[n] = 0;
        }
        else if (who == 0 && visit[i] == 0 && IJ[n] == 0)
        {
            IJ[n] = i;
            total += Sij(i, n + 1, who);
            IJ[n] = 0;
        }
    }
 
    return total;
}
 
void DFS(int cur, int n)
{
    if (n == N / 2)
    {
        int A = Sij(-1, 0, 1);
        IJ[0] = IJ[1] = 0;
        int B = Sij(-1, 0, 0);
        IJ[0] = IJ[1] = 0;
 
        int m = abs(A, B);
            if (m < MIN)
                MIN = m;
 
        return;
    }
 
    for (int i = cur + 1; i <= N; i++)
    {
        if (visit[i] == 0)
        {
            visit[i] = i;
            DFS(i, n + 1);
            visit[i] = 0;
        }
    }
 
    return;
}
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        MIN = 987654321;
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        scanf("%d", &N);
 
        for (int a = 1; a <= N; a++)
            for (int b = 1; b <= N; b++)
                scanf("%d", &map[a][b]);
 
        DFS(0, 0);
 
        printf("#%d %d\n", T, MIN);
    }
 
    return 0;
}