백준 14889 : 스타트와 링크

💡기본 정보

유형
: 시뮬레이션
풀이 날짜
: 2025년 01월17일 
풀이방법 한줄 요약
: 스타트팀과 링크팀에 능력치 조합을 구해서 최솟값을 구하는 방식

 

💡문제에서 구해야 할 것

N은 짝수이고 N/2명으로 스타트팀과 링크 팀으로 사람이 나눠짐
사람에게 번호를 1부터 N까지 배정하고 능력치를 조사 

능력치 Sijsms i번 사람과 j번 사람이 같은 팀에 속했을 때 팀에 더해지는 능력치 

팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합 

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

💡알고리즘 설계

- 스타트 팀과 링크 팀에 각 2명씩 가능한 조합의 능력치를 계산

- 최종적으로 스타트 팀과 링크 팀의 능력치 차이의 최솟값 계산

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().trim().split("\n");
const N = parseInt(input[0]);
const table = input.slice(1).map(line => line.split(" ").map(Number));
let answer = Number.MAX_SAFE_INTEGER;

function team(){
    const visit = Array(N).fill(false);
    check(0,0,visit);
    return answer
}

function check(member, start, visit){
    if(member === N/2){
        let startTeam = 0;
        let linkTeam = 0;
        for(let i =0;i<N;i++){
            for(let j = 0 ; j < N; j++){
                if(visit[i]&&visit[j]){
                    startTeam += table[i][j];
                }else if(!visit[i]&&!visit[j]){
                    linkTeam += table[i][j];
                }
            }
        }
        answer = Math.min(answer,Math.abs(startTeam-linkTeam));
    }
    for(let i = start; i < N ; i++){
        if(!visit[i]){
            visit[i]=true;
            check(member+1 , i+1, visit)
            visit[i]=false;
        }
    }
}
console.log(team());

 

💡시간복잡도

 

💡 틀린 이유 & 틀린 부분 수정

처음에는 2명씩 팀에 들어가있는 걸 모르고 전부 들어가는 경우의 수로 계산하는 로직으로 작성해 문제가 발생함 

 

💡 다른 풀이 or 기억할정보

Math.abs() :절댓값 구하기

let answer = Number.MAX_SAFE.INTEGER; 
 : Math.min을 쓸 때는 Number타입의 최대로 설정해놓고 사용해야함 . (Max의 경우는 0)