Boj 14889) 스타트와 링크

문제

백준 14889

설명

기본적으로 조합만 구현하면 제한시간 내에 풀리는 문제이나 여기에 추가로 할 수 있는 2가지 최적화가 인상깊었다.

첫번째는 전체 그룹을 두 그룹으로 나누므로써 생기는 중복 제거이다. 이는 임의의 원소 한개를 한쪽 그룹에 미리 넣어두어 두 그룹 간의 대칭성을 제거하므로써 해결할 수 있다. 그러면 전체 경우의 수가 반으로 줄어들게 된다.

두번째는 비용을 구할 때 2중 포문을 1중 포문으로 바꾸는 것이다. 기본적인 아이디어는 문제의 정의 상, 전체 비용 행렬에서 스타트 내의 인덱스를 행 또는 열로 접근하는 비용을 제외하면 링크 의 비용이라는 것을 이용한다. 그래서 링크의 비용을 구하기 위해 전체 비용 행렬을 행과 열 단위로 구분해서 전처리하면 중복되는 구간이 생긴다. 그리고 이 중복되는 구간이 절묘하게도 스타트의 비용이 된다. 그래서 아래처럼 간결한 코드가 성립하게 된다.

시간 복잡도

O(\(\mathrm{N} {\mathrm{N}\choose\mathrm{N/2}}\))

코드

int n, ans = 1e9;
int s[20], r[20], total;
int sss[20];

void Select(int cur = 0, int th = 0)
{
	if (th == n / 2)
	{
		int res = 0;
		for (int i = 0; i < th; i++)
			res += s[sss[i]] + r[sss[i]];

		ans = min(abs(total - res), ans);
		return;
	}

	for (int i = cur; i < n; i++)
	{
		swap(sss[th], sss[i]);
		Select(i + 1, th + 1);
		swap(sss[th], sss[i]);
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) sss[i] = i;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		int tmp; cin >> tmp;
		total += tmp;
		s[i] += tmp;
		r[j] += tmp;
	}
	Select(1);  // 0 이 아니라 1로서 경우의 수가 반절로 줄음
	cout << ans;
}