baekjoon. 스타트와 링크

문제

링크

풀이

백트래킹을 이용해서 팀을 어떻게 조합할지 결정한 후

각 팀의 점수를 구해서 빼주고 절대값을 구해서 그 중최소값을 출력하면된다

코드

    function solution(input){
        const N = input.split('\n')[0]*1;
        const board = input.split('\n').slice(1).map(v=>v.split(' ').map(v=>v*1));
        const arr = Array(N).fill().map(()=>false);

        let answer = Infinity;

        btk(0,0);

        console.log(answer);

        function btk(idx, cnt){
            if(cnt=== Math.floor(N/2)){
                let start = 0;  
                let link = 0;
                for (let i = 0; i < N; i++) {
                    for (let j = 0; j < N; j++) {
                        if (i === j) continue;
                        if (arr[i] && arr[j]) {
                            start += board[i][j];
                        } else if (!arr[i] && !arr[j]) {
                            link += board[i][j];
                        }
                    }
                }
                answer = Math.min((Math.abs(start-link)), answer);
                return ;
            }

            for(let i= idx; i<arr.length;i++){
                arr[i]= true;
                btk(i+1,cnt+1);
                arr[i]= false;
            }
        }
    }