[백준 - node.js] 스타트와 링크 14889번

문제 설명

 

핵심

 

1. 팀 구성에 대한 모든 경우의 수를 구하기

 

2. 각 팀에서 얻을 수 있는 모든 능력치의 합을 구하기

 

---

문제 풀이

 

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

let input = [];
let n = 0;
let count = 0;

rl.on('line', function (line) {
  if (!count) n = +line;
  else input.push(line.split(' ').map(e => +e));
  count++;
}).on('close', function () {
  solution(input);
  process.exit();
});

const solution = input => {
  // 초기세팅
  const visited = new Array(n).fill(false);
  const arr = [];
  let a = [];
  let b = [];
  let min = Infinity;
  let aSum = 0;
  let bSum = 0;

  // dfs
  const dfs = (count, idx) => {
    // base case => arr(한 팀)의 자릿수가 n / 2 일때
    if (count === n / 2) {
      // 구해준 arr를 활용하여 반대쪽 팀을 구해준다
      // A팀, B팀으로 나누어줌
      for (let i = 0; i < n; i++) {
        if (arr.includes(i)) a.push(i);
        else b.push(i);
      }
    // 이중 for문을 활용하여 모든 경우의 팀능력치를 구해준다
      for (let i = 0; i < a.length; i++) {
        for (let j = i + 1; j < a.length; j++) {
          aSum += input[a[i]][a[j]] + input[a[j]][a[i]];
          bSum += input[b[i]][b[j]] + input[b[j]][b[i]];
        }
      }
      min = Math.min(min, Math.abs(aSum - bSum));
      // 초기화
      aSum = 0;
      bSum = 0;
      a = [];
      b = [];
    }
    // 순회하여 팀으로 구성 될 모든 경우의 수를 구해준다.
    for (let i = idx; i < n; i++) {
      if (!visited[i]) {
        arr.push(i);
        visited[i] = true;
        dfs(count + 1, i);
        arr.pop();
        visited[i] = false;
      }
    }
  };
  dfs(0, 0);
  console.log(min);
};

 

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

14889번: 스타트와 링크