function getPermutation(arr, selectNum) {
let result = [];
if (selectNum === 1) return arr.map((v) => [v]);
arr.forEach((v, idx, arr) => {
const fixer = v;
const restArr = arr.filter((_, index) => index !== idx);
const permuationArr = getPermutation(restArr, selectNum - 1);
const combineFixer = permuationArr.map((v) => [fixer, ...v]);
result.push(...combineFixer);
});
return result;
}
function solution(n, weak, dist) {
let answer = 10;
const arr = [...weak];
let permutation = [];
if (weak.length === 1) return 1;
for (let i=1; i<=dist.length; i++) {
const permu = getPermutation(dist, i);
permutation = permutation.concat(permu);
}
for (let i=0; i<weak.length; i++) {
for (const value of permutation) {
const selected = [...value];
const wall = [...arr];
let now = wall.shift();
while (selected.length > 0) {
if (wall[0] - now <= selected[0]) {
wall.shift();
} else {
now = wall[0];
selected.shift();
}
}
if (wall.length === 0) {
if (answer > value.length) answer = value.length;
}
}
arr.push(arr.shift() + n);
}
return answer === 10 ? -1 : answer;
}풀이
dist의 길이가 최대 8로 크지 않기 때문에, 가능한 모든 방법을 탐색해서 해결할 수 있다.
따라서 dist에서 친구 한명을 선택해 나열하는 방법, 2명을 선택해 나열하는 방법 ~ n명을 선택해 나열하는 방법을 모두 고려해주면 된다.
순서가 상관 있기 때문에 순열 알고리즘을 사용한다.
이제 각각의 방법에 대해 취약지점을 모두 점검할 수 있는지 확인한다. 확인하는 방법은 친구 한명을 배정한 다음 아직 점검하지 않은 지점 중에서 바로 다음 지점에 친구를 순서대로 배정하면 된다.
배정을 마친 후에도 아직 점검하지 않은 취약지점이 남아있다면 해당 배치 방법으로는 모든 취약지점을 점검할 수 없다는 뜻이다.
이제, 원형으로 이루어진 벽을 고려하기 위해, 다음 시작 지점을 기준으로 직선으로 펼쳐주면 된다.
예를 들어, N = 12, weak = [1, 5, 6, 10]인 경우 처음에 위치 1을 기준으로 직선으로 펼쳤다면, 이번엔 위치 5를 기준으로 [5, 6, 10, 13]과 같이 직선 형태로 만들어주면 된다. 이때, 13은 1 + N을 해준 결과이다.
결론!
각 친구들을 선택해 나열하는 방법에 대해서 모든 시작 지점에 대해 직선으로 펼친 후 취약 지점에 배정해본 다음, 그중 가장 적은 친구들을 선택하는 방법을 찾으면 된다.
