[boj] 14889. 스타트와 링크 (node.js)

문제 요약

[boj] 14889. 스타트와 링크 (node.js)

풀이

• 문제 조건에 따른 팀을 구성할 수 있도록 탐색한 후, 탐색 결과를 활용해 값을 계산해주면 되는 문제다.
• 팀에 속하는 사람을 뽑는 경우의 수를 겹치지 않게 하기 위해 startIdx 를 인자로 활용해 오름차순으로 뽑았다. for (let i = startIdx;

내 풀이

const readline = require("readline")
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
})

const solution = () => {
  const N = Number(input())
  let arr = []
  for (let i = 0; i < N; i++) arr.push(input().split(" ").map(Number))
  let disc = Infinity
  let used = new Array(N).fill(0)
  rec(0, 0)
  console.log(disc)

  function rec(k, startIdx) {
    if (k == N / 2) {
      disc = Math.min(getDisc(), disc)
      return
    }
    for (let i = startIdx; i < N; i++) {
      if (used[i]) continue
      used[i] = 1
      rec(k + 1, i)
      used[i] = 0
    }
  }

  function getDisc() {
    let team = [0, 0]
    for (let i = 0; i < N; i++) {
      for (let j = i + 1; j < N; j++) {
        if (used[i] != used[j]) continue
        let score = arr[i][j] + arr[j][i]
        team[used[i]] += score
      }
    }
    return Math.abs(team[0] - team[1])
  }
}

let line = 0
const input = () => stdin[line++]

let stdin = []
rl.on("line", function (line) {
  stdin.push(line)
}).on("close", function () {
  solution()
  process.exit()
})

주절주절

• 98%에서 오류가 발생해서 못 풀고 있던 문제인데, used 배열을 초기화해두지 않아서 예외가 발생하면 틀리는 경우가 있었다. 언제나 초기화에 유의하자!