어떤 문제인가?

문제의 조건이 특별한, 모든 경우의 수를 대입해 최소값을 찾는 문제.

문제의 조건

1. 몇 번째 선수를 언제 뽑건 순서는 중요하지 않다.

   (1, 2, 3, 4) 나 (4, 2, 1, 3) 이나 동일하다.

2. 거울상 꼴이다. 이게 제일 중요하다.

   N=6 이라고 칠 때, 1-5-6을 뽑으면 남는 건 2-3-4.
   다음 탐색 때 2-3-4를 뽑으면 남는 건 1-5-6.
   앞서 말한 1. 특성에 의거, 이는 중복되는 조합이다.

근데 이걸 왜 3번이나 틀림?

... $4 \leq N \leq 20$ 조건을 제대로 안본 내 잘못이지.

#include <stdio.h>
#include <stdlib.h>

int N,m=2<<20,S[21][21];
char u[21]={0,1};

void d(int l,int k) {
    int i,j,k1=0,k2=0;
    if(l==N/2) {
        for(i=1;i<=N;i++) {
            for(j=i+1;j<=N;j++) {
                if(!u[i]^u[j]) {
                    if(u[i]) k1+=(S[i][j]+S[j][i]);
                    else k2+=(S[i][j]+S[j][i]);
                }
            }
        }
        if(m>abs(k1-k2)) m=abs(k1-k2);
        if(m>abs(k2-k1)) m=abs(k2-k1);
        return;
    }
    
    for(i=k;i<=N;i++) {
        if(!u[i]) {
            u[i]=1;
            d(l+1,i+1);
            u[i]=0;
        }
    }
}

int main() {
    int i,j;
    scanf("%d",&N);
    for(i=1;i<=N;i++) {
        for(j=1;j<=N;j++) {
            scanf("%d",&S[i][j]);
        }
    }
    d(1,2);
    printf("%d",m);
}

S[21][21]

고치기 전까진 S[11][11]이었다. 아, 제발...

적용 가능한 최적화

그냥 생각없이 뽑으면 $N!$ 번의 연산을 거쳐야 한다.

시간 초과나기 딱 좋은 연산량이다.

1. 오름차순 정렬
   N과 M 시리즈를 풀어본 사람은 알 것이다.
2. 선수 선발 시 맨 처음 선수는 1로 고정
   이렇게 하면 $20!$이 $\frac{20!}{10!}$으로 줄어든다.
3. 스타트 팀과 링크 팀 능력치를 담는 배열을 따로 생성 후 사용
   이렇게 하면 $O(N^2)$ 작업에서 $N$이 $\frac{N}{\sqrt{2}}$이 된다.

다른 사람들의 풀이

전체적으로 비슷한데, 배열을 써서 저장하고 담는 경우가 많았다. 물론 그렇게 하는게 시간적으로 더 빠르기도 하고.

#include <stdio.h>

int s[20][20], n, m = 20000, n2;
char u[20];

void check() {
	int i, j, a[10], b[10], ai, bi;
	for (i = ai = bi = 0 ; i < n ; i++) {
		if (u[i]) a[ai++] = i;
		else b[bi++] = i;
	}
	ai = bi = 0;
	for (i = 0 ; i < n2 ; i++) {
		for (j = i + 1 ; j < n2 ; j++) {
			ai += s[a[i]][a[j]] + s[a[j]][a[i]];
			bi += s[b[i]][b[j]] + s[b[j]][b[i]];
		}
	}
	if ((ai -= bi) < 0) ai = -ai;
	if (ai < m) m = ai;
}

void recur(int k, int d) {
	int i;
	if (d == n2) {
		check();
		return;
	}
	for (i = k + 1 ; i < n ; i++) {
		u[i] = 1;
		recur(i, d + 1);
		u[i] = 0;
	}
}

int main() {
	int i, j;

	scanf("%d", &n);
	n2 = n >> 1;
	for (i = 0 ; i < n ; i++) {
		for (j = 0 ; j < n ; j++) {
			scanf("%d", &s[i][j]);
		}
	}
	recur(-1, 0);
	printf("%d", m);
}

goooora님 소스
-> https://www.acmicpc.net/source/8061673

하.. 배열 크기 잘못 잡은 것 때문에 몇시간을 삽질한건지?