백준 14889번: 스타트와 링크 - javascript

3 분 소요

백준 14889번: 스타트와 링크

문제 설명

접기/펼치기

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j	1	2	3	4
1		1	2	3
2	4		5	6
3	7	1		2
4	3	4	5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

스타트 팀: S12 + S21 = 1 + 4 = 5
링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

스타트 팀: S13 + S31 = 2 + 7 = 9
링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

접기/펼치기

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

접기/펼치기

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예시

접기/펼치기

출력
2

접근

1부터 주어진 범위 N까지의 수에서 N/2개를 골라 2개의 수열 집합을 만들고, 각각의 집합에서 모두 서로 악수하는 경우의 합의 차이 중 최소값을 고르는 문제다 ??

일단, N명중에서 절반만 스타트팀으로 데려오는 모든 경우를 찾아야한다. 어차피 스타트팀이 생기면 링크팀은 자연스레 알게된다.
그러기 위해서는 N과 M 시리즈에서 풀었던 재귀 방법을 다시 참조 할 필요가 있다.
깊이가 N/2까지인 재귀함수에서 i부터 N까지의 수 중에서 수열을 만든다.
다만 back이라는 조건 함수를 추가해서 중복체크와는 별개로 [0,1] 과 [1,0]같은 순서만 다른 동일한 구성의 수열의 경우를 배제한다.
= 사실상 오름차순의 형식으로 수열을 구하게 된다.

한 개의 수열, 팀을 구성하게 되면 그때마다 team을 만들어주는 함수를 호출한다.
이 함수에서는 위의 재귀함수에서 구한 스타트팀을 이용해서 반복문을 돌려가며 0부터 N-1까지 스타트팀에 없는 사람을 링크팀에 넣어준다.
이렇게 구한 스타트팀과 링크팀을 능력치계산 함수에 넣어 둘의 차이를 계산해서 min값과 비교해서 min값을 업데이트해준다.

능력치 계산 함수에서는 간단하다.
모든 사람간의 Sij와 Sji 능력치를 합해야 서로의 능력치 시너지 값이므로 이중 반복문을 돌려서 i와 j값이 다른 모든 경우의 stats배열 값을 누산하여 최종적으로 반환해준다.
이 반환된 값은 위에 team을 만들어주는 함수에서 스타트팀과 링크팀의 차이를 계산하는데 쓰인다.

최종적으로 재귀함수가 끝나게 되면 모든 계산이 끝날 것이고 우리는 전역변수 min값을 출력해주면 끝이다.

ps
처음에는 정답코드에서 매번 min값을 업데이트 해주지 않고 전역 배열에 저장해 두었다.
그리고 그때마다 매번 스타트 팀과 링크 팀의 목록도 객체로 저장했는데 그랬더니 런타임 에러가 떠버렸다.
~~배열들은 그냥 내가 코드의 내부적인 결과 값들을 검산하기 위함이기도 했다.~~
아마 전역 배열을 너무 많이 지정해서 메모리 초과가 난듯해서 전부 지우고 위에서 풀이한데로 min값을 계속 비교해서 갱신해주는 방식으로 바꿨더니 통과됬다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let list = [];
let stats = [];
let result = [];
let min = 20*100+1;
let check = new Array(20).fill(false);
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let n = input.splice(0,1);  
  for(let i =0;i<n;i++){
    stats.push(input[i].split(' ').map(el => el*1));
  }  
  re(0,n,n/2,0,-1);
  console.log(min)
  process.exit();
});

//한 팀을 구성할때 마다 호출하는 함수
let set_team = function(value, n){
  let a_team = value.split(' ').map(el => el*1);
  let b_team = [];
  for(let i=0;i<n;i++){
    if(a_team.indexOf(i)==-1)b_team.push(i);
  }  
  min = Math.min(min, (Math.abs(cal_re(a_team)-cal_re(b_team))));
  return ;
}
//팀들의 능력치값의 합을 계산하는 함수
let cal_re = function(team){
  let sum = 0;
  for(let i=0; i<team.length; i++){
    for(let j=0; j<team.length; j++){
      if(i!==j)sum+=stats[team[i]][team[j]];
    }
  }
  return sum;
}
//N/2명의 팀원을 구성하는 모든 경우를 위한 재귀함수
let re = function(cnt,n,m,start,back){
  if(cnt==m){    
    set_team(list.join(' '), n);
    return ;
  }
  for(let i=start;i<n;i++){    
    if(!check[i]&&i>back){      
      check[i] = true;      
      list[cnt] = i
      re(cnt+1,n,m,start,i);      
      check[i] = false;
    }
  }
  return ;
}

Twitter Facebook LinkedIn

ryeon

백준 14889번: 스타트와 링크 - javascript