[백준] 14889 스타트와 링크 - JavaScript(NodeJS)

문제

14889번: 스타트와 링크

 

풀이

4명의 능력치 배열

 

항상 짝수인 N명의 사람들이 있다.

 

스타트 팀에 N/2명이 들어가는 모든 경우의 수를 구하고, 스타트팀이 아닌 사람은 링크팀에 넣어준다.
그리고 문제에서 주어진 것과 같이, 각 팀 별로 능력치의 합계를 구하고, 차이의 최솟값을 구하면 된다.

 

N은 짝수이며 4<=N<=20이므로 모든 경우의 수를 조회해도 시간 제한 내에서 충분하다.

 

※ 능력치를 구할 때 유의할 점

 

스타트팀 = [1,2,3] 일 때 모든 (x,y) 쌍을 구한다.
그리고 모든 쌍 (1,2), (2,1), (1,3), (3,1), (2,3), (3,2) 를 더해줘야 팀의 능력치를 구할 수 있다.

 

코드

const sol = (input) => {
  const N = +input[0];
  const halfN = N / 2;
  const stats = input.slice(1).map((str) => str.split(" ").map(Number));

  const check = new Array(N).fill(0);
  let min = Number.MAX_SAFE_INTEGER;
  function dfs(L, K) {
    if (L === halfN) { // 스타트팀에 N/2 명이 뽑혔다면
      const sTeam = [];
      const lTeam = [];
      let sSum = (lSum = 0);
      for (let i = 0; i < N; i++) {
        if (check[i]) sTeam.push(i); // 체크 배열은 스타트 팀에 넣어주고, 체크 배열에 없으면 링크 팀에 넣어준다.
        else lTeam.push(i);
      }
      for (let i = 0; i < halfN; i++) {
        for (let j = i + 1; j < halfN; j++) { // (i,j), (j,i) 쌍을 계속 더해준다.
          sSum = sSum + stats[sTeam[i]][sTeam[j]] + stats[sTeam[j]][sTeam[i]];
          lSum = lSum + stats[lTeam[i]][lTeam[j]] + stats[lTeam[j]][lTeam[i]];
        }
      }
      min = Math.min(min, Math.abs(sSum - lSum));
      return;
    }

    for (let i = K; i < N; i++) { // 체크 배열을 스타트 팀 구성에 사용한다.
      check[i] = 1;
      dfs(L + 1, i + 1);
      check[i] = 0;
    }
  }
  dfs(0, 0);
  return min;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });