문제 링크
https://www.acmicpc.net/problem/2110
풀이 전략
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
코드
const fs = require("fs");
const input = fs
.readFileSync("/dev/stdin")
.toString()
.trim()
.split(/\s/)
.map(Number);
const n = input.shift(); // 사용하지 않는다.
const c = input.shift();
solution(input);
function solution(arr) {
arr.sort((a, b) => a - b);
let lt = 1;
let rt = arr[arr.length - 1];
while (lt <= rt) {
const mid = ~~((lt + rt) / 2);
if (calDis(arr, mid) >= c) lt = mid + 1;
else rt = mid - 1;
}
console.log(rt);
}
function calDis(arr, mid) {
let cnt = 1;
let curPos = arr[0];
for (const pos of arr) {
if (pos - curPos >= mid) {
cnt++;
curPos = pos;
}
}
return cnt;
}
회고
집의 좌표가 0과 1,000,000,000사이인 것을 보고 이분탐색을 떠올렸다. 조금 더 범위가 작았더라면 다른 알고리즘을 떠올릴 수 있겠지만 넓은 범위를 탐색하기 위해서는 이분 탐색만큼 빠른 것은 찾아 보기 힘들기에 이분탐색으로 문제를 풀기로 하였다.
어떤 알고리즘을 사용할지 결정을 하였다면 이에 따라 구현하는 것은 그리 어렵지 않았다.
더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)
'Algorithm > 백준[BOJ]' 카테고리의 다른 글
[JS] 백준 10814번 나이순 정렬 (0) | 2022.07.12 |
---|---|
[JS] 백준 1300번 K번째 수 (0) | 2022.07.08 |
[JS] 백준 2630번 색종이 만들기 (0) | 2022.06.16 |
[JS] 백준 18258번 큐2 (0) | 2022.06.14 |
[JS] 백준 1874번 스택 수열 (0) | 2022.06.11 |
댓글