백준 14889번 - 스타트와 링크 (Go)

https://www.acmicpc.net/problem/14889

분석

이 문제는 n 명 중 n / 2 명을 뽑는 문제입니다. 뽑는 것에 순서는 필요가 없으니 조합 문제 입니다.

N=20 이라는 작은 입력 크기 덕분에 브루트 포스와 백트래킹으로 가능합니다.

시간 복잡도는 4 <= n <= 20, O(20C10) = 184,756 이고, O(n2) = 400 이므로

184,756 * 400 = 7300만 으로 시간 제한에 여유롭습니다.

공간 복잡도는 int 형 O(n2) = 8byte * 400 = 3200 byte 으로 여유롭습니다. 

풀이 코드

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var (
	n int
	powers [][]int
	visited []bool
	res = math.MaxInt32
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	fmt.Fscan(in, &n)

	powers = make([][]int, n)
	for i := 0; i < n; i++ {
		powers[i] = make([]int, n)

		for j := 0; j < n; j++ {
			fmt.Fscan(in, &powers[i][j])
		}
	}

	visited = make([]bool, n)
	solution(0, 0)

	fmt.Fprintln(out, res)
}

func solution(idx, cnt int) {
	if cnt == n / 2 {
		calcDiff()
		return
	}

	for i := idx; i < n; i++ {
		if !visited[i] {
			visited[i] = true
			solution(i + 1, cnt + 1)
			visited[i] = false
		}
	}
}

func calcDiff() {
	startSum := 0
	linkSum := 0

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if visited[i] && visited[j] {
				startSum += powers[i][j]
			} else if !visited[i] && !visited[j] {
				linkSum += powers[i][j]
			}
		}
	}

	diff := int(math.Abs(float64(startSum - linkSum)))
	if diff < res {
		res = diff
	}
}

회고

팀 분리를 어떻게 할지 고민이 됐던 문제였습니다.