[백준] 14889 스타트와 링크

Kang DongHa·2024년 7월 25일

문제

https://www.acmicpc.net/problem/14889

내가 푼 방법

const filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";
const input = require("fs")
    .readFileSync(filePath)
    .toString()
    .trim()
    .split("\n");

const N = Number(input.shift());
const ability = input.map((el) => el.split(" ").map(Number));

function getCombinations(arr, selectNum) {
    if (selectNum === 1) return arr.map((el) => [el]);

    const result = [];

    arr.forEach((fixed, idx, origin) => {
        const rest = origin.slice(idx + 1);
        const combinations = getCombinations(rest, selectNum - 1);
        const attached = combinations.map((combination) => [
            fixed,
            ...combination,
        ]);

        result.push(...attached);
    });

    return result;
}

function getPermutations(arr, selectNum) {
    if (selectNum === 1) return arr.map((el) => [el]);

    const result = [];

    arr.forEach((fixed, idx, origin) => {
        const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)];
        const permutations = getPermutations(rest, selectNum - 1);
        const attached = permutations.map((permutation) => [
            fixed,
            ...permutation,
        ]);

        result.push(...attached);
    });

    return result;
}

const combinations = getCombinations(
    new Array(N).fill().map((_, idx) => idx),
    N / 2
);
let min = 10000000;

for (let i = 0; i < combinations.length; i++) {
    let start = 0;
    let link = 0;

    // 스타트팀
    for (const [a, b] of getPermutations(combinations[i], 2)) {
        start += ability[a][b];
    }

    const linkTeam = new Array(N)
        .fill()
        .map((_, idx) => idx)
        .filter((el) => !combinations[i].includes(el));

    // 링크팀
    for (const [a, b] of getPermutations(linkTeam, 2)) {
        link += ability[a][b];
    }

    min = Math.min(min, Math.abs(start - link));
}

console.log(min);

N/2개를 뽑는 조합을 만들어 start팀으로, 그 외의 것들을 link팀으로 설정
능력치의 합을 구하고 기존 min값과 비교하여 최소값 산정

개선이 가능했던 부분(내 생각)

능력치의 총 합을 구하는 부분의 코드가 중복되기에 해당 코드를 함수로 만들어 중복을 줄인다.

function carculateTeamAbility(team) {
    let result = 0;

    for (const [a, b] of getPermutations(team, 2)) {
        result += ability[a][b];
    }

    return result;
}

... 중략

const start = carculateTeamAbility(combinations[i]);
const link = carculateTeamAbility(linkTeam);

능력치의 총 합을 구하는 함수에서 순열을 사용하지말고 이중 for문을 사용하도록 개선

function carculateTeamAbility(team) {
    let result = 0;

    for (let i = 0; i < team.length; i++) {
        for (let j = 0; j < team.length; j++) {
            result += ability[team[i]][team[j]];
        }
    }

    return result;
}

i와 j가 같더라도 ability표에서는 0이기에 예외처리 안했지만, 필요하다면 if(x !== y)등의 예외처리가 필요하다.

실제로 실행시간을 많이 줄였다 !!

사실 백트래킹 단계의 문제였다..

백트래킹 단계의 문제를 풀면서 백트래킹을 사용하지 않았다.. 그래서 백트래킹을 이용한 풀이를 찾아보며(아직 익숙하지 않다..) 백트래킹 공부를 해보자.

const filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";
const input = require("fs")
    .readFileSync(filePath)
    .toString()
    .trim()
    .split("\n");

const N = Number(input.shift());
const ability = input.map((line) => line.split(" ").map(Number));

function calculateTeamAbility(team) {
    let sum = 0;
    for (let i = 0; i < team.length; i++) {
        for (let j = 0; j < team.length; j++) {
            sum += ability[team[i]][team[j]];
        }
    }
    return sum;
}

let min = Infinity;

function dfs(index, teamStart) {
    if (teamStart.length === N / 2) {
        const teamLink = [];
        for (let i = 0; i < N; i++) {
            if (!teamStart.includes(i)) {
                teamLink.push(i);
            }
        }
        const start = calculateTeamAbility(teamStart);
        const link = calculateTeamAbility(teamLink);
        min = Math.min(min, Math.abs(start - link));
        return;
    }

    for (let i = index; i < N; i++) {
        teamStart.push(i);
        dfs(i + 1, teamStart);
        teamStart.pop();
    }
}

dfs(0, []);
console.log(min);