[백준 15661] 링크와 스타트
March 07, 2023
문제
https://www.acmicpc.net/problem/15661
아이디어
각 팀의 인원수는 반드시 같아야 할 필요는 없지만, 최소한 한 명의 멤버는 팀 내에 존재해야 한다.
그렇기에 스타트 팀의 멤버가 1명일 때부터 n-1명일 때까지의 멤버를 구성하는 경우의 수를 조합을 활용해서 구하고
각 경우의 수에서 스타트 팀으로 선택받지 못한 멤버는 모두 링크 팀으로 설정한다.
그 다음에는 각 팀간의 파워를 계산해서 팀간의 파워차가 최소치가 되도록 하면 된다.
소스코드
// 입력 처리
const INPUT_NAME = 'i2.txt';
const filePath = process.platform === 'linux' ? '/dev/stdin' : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require('fs').readFileSync(filePath).toString().trim().split('\n').map(item => item.trim());
const n = Number(input[0]);
// 능력치 데이터
const map = [];
for (let i = 1; i <= n; i++) {
map.push(input[i].split(' ').map(e => Number(e)));
}
// 팀의 파워를 구한다.
function getTeamPower(team) {
let sum = 0;
team.forEach(target => {
team.forEach(other => {
sum += map[target][other];
});
});
return sum;
}
// n명의 멤버 중에서 r명의 멤버를 선택하는 조합을 구하고, 그 조합에 대해 callback 함수를 실행한다.
function combination(r, callback) {
const result = [];
const DFS = function(depth, begin) {
if (depth === r) {
callback(result);
return;
}
for (let i = begin; i < n; i++) {
result[depth] = i;
DFS(depth + 1, i + 1);
}
}
DFS(0, 0);
}
// 문제
function solution() {
let result = Number.MAX_SAFE_INTEGER;
// 스타트 팀의 멤버를 1명부터 n-1명까지 늘리면서 경우의 수(조합)을 구한다.
for (let r = 1; r < n - 1; r++) {
combination(r, function(startTeam) {
const linkTeam = Array.from({ length: n }, (_, i) => i).filter(i => !startTeam.includes(i)); // 스타트 팀 멤버가 아닌 멤버를 모두 링크 팀으로 한다.
const startPower = getTeamPower(startTeam); // 스타트 팀의 파워를 구한다.
const linkPower = getTeamPower(linkTeam); // 링크 팀의 파워를 구한다.
result = Math.min(result, Math.abs(startPower - linkPower)); // 양 팀간의 파워 차이를 최소한으로 하는 값을 구한다.
});
}
console.log(result);
}
// 실행
solution();