ํฐ์คํ ๋ฆฌ ๋ทฐ
๐ฉ๐ป๐ป ๋ฌธ์
โ๐ป ํ์ด
๐จ Go
package main
import (
"fmt"
"os"
"bufio"
"math"
)
var (
n int
result = 1000
numbers [][]int
visited = make([]bool, 21)
)
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
fmt.Fscanln(reader, &n)
numbers = make([][]int, n)
for i := range numbers {
numbers[i] = make([]int, n)
}
for i:=0; i<n; i++ {
for j:=0; j<n; j++ {
fmt.Fscanf(reader, "%d ", &numbers[i][j])
}
}
dfs(0, 0)
fmt.Fprintln(writer, result)
}
func dfs(index, len int) {
if n/2 == len {
computeResult()
} else {
for i := index + 1 ; i < n; i++ {
if !visited[i] {
visited[i] = true
dfs(i, len + 1)
}
}
}
visited[index] = false
}
func computeResult() {
start := make([]int, n/2)
link := make([]int, n/2)
var startIdx, linkIdx int
for i:=0; i<n; i++ {
if visited[i] {
start[startIdx] = i
startIdx++
} else {
link[linkIdx] = i
linkIdx++
}
}
var diff, startTotal, linkTotal int
for i:=0; i<n/2; i++ {
for j:=i+1; j<n/2; j++ {
startTotal = startTotal + numbers[start[i]][start[j]] + numbers[start[j]][start[i]]
linkTotal = linkTotal + numbers[link[i]][link[j]] + numbers[link[j]][link[i]]
}
}
diff = int(math.Abs(float64(linkTotal-startTotal)))
if diff < result {
result = diff
}
}
728x90
'dev > algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
BOJ / 1003๋ฒ / ํผ๋ณด๋์น ํจ์ [Go] (0) | 2020.08.01 |
---|---|
BOJ / 2748๋ฒ / ํผ๋ณด๋์น ์ 2 [Go] (0) | 2020.07.31 |
BOJ / 14888๋ฒ / ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ [Go] (0) | 2020.07.29 |
BOJ / 2580๋ฒ / ์ค๋์ฟ [Go] (0) | 2020.07.24 |
BOJ / 9663๋ฒ / N-Queen [Go] (0) | 2020.07.23 |
๋๊ธ
๊ธ ๋ณด๊ดํจ
์ต๊ทผ์ ๋ฌ๋ฆฐ ๋๊ธ
TAG
- baekjoon
- AWS
- go
- python3
- ํ๋ก์ด๋์์ฌ
- ๋ฐฑ์ค
- ์ด๋ถํ์
- ๋งฅ๋ถํ๋ก
- ์๋ฐ
- ์คํ
- ์๊ฐ๊ต์ฒด
- dp
- java
- Macbook pro 2012 mid 13
- ๋งฅ๋ถ ์ ๊ทธ๋ ์ด๋
- ํ
- ๋ชฝ๊ณ ๋๋น
- ๋ธ๋ฃจํธํฌ์ค
- BFS
- ์๊ณ ๋ฆฌ์ฆ
- dfs
- ballet
- BOJ
- ํด์๋งต
- Algorithm
- MongoDB
- ๋งฅ๋ถ
- Golang
- ๋ฐ๋
- ๋ถํ ์ ๋ณต
- Total
- Today
- Yesterday