백준 스타트와 링크

풀이

크게 두 가지 작업으로 나뉜다.
1. 백트래킹을 이용한 팀 나누기
2. 나눠진 팀에 대해 각각 포인트 계산 및 반환

백트래킹 알고리즘에 대해 이해하고 있다면 큰 어려움 없이 해결할 수 있는 문제이다.

소스코드

const input = require('fs').readFileSync('./dev/stdin').toString().trim().split('\r\n');


let n = +input[0];
let S = [];
for(let i=1;i<input.length;i++){
  S.push(input[i].split(' ').map(x=>+x));
}

function calcPoint(team){
  let res=0;
  for(let i=0;i<team.length;i++){
    for(let j=i+1;j<team.length;j++){
      res+=S[team[i]][team[j]];
      res+=S[team[j]][team[i]];
    }
  }
  return res;
}

function btrc(team,idx,cnt){
  if(cnt==n/2){
    let team2 = [];
    for(let i=0;i<n;i++) {
      if(team.indexOf(i)<0) {
        team2.push(i);
      }
    }
 
    return Math.abs(calcPoint(team)-calcPoint(team2));
  }
  else if(idx==n) return Infinity;
  else{
    
    team.push(idx)
    let res = btrc(team,idx+1,cnt+1)
    team.pop();

    return Math.min(res,btrc(team,idx+1,cnt));
  }
}

let team=[]
console.log(btrc(team,0,0));

후기

team2 의 멤버를 구하기 위해 사용한 indexOf의 시간복잡도가 O(N) 인데 모든 멤버에 대해 사용하므로 최악의 경우 대략 20*20 의 연산이 요구된다. N값이 크지 않아 그냥 사용했지만 visit 배열을 사용했다면 20번의 연산안에 해결되므로 조금 더 빠른 시간 안에 해결할 수 있을 것 같다.