랜선 자르기

문제

언어

  • JavaScript

문제 풀이 step 1

  • 오름차순으로 정렬합니다.
  • 1과 배열의 최댓값을 기준으로 이진 탐색을 진행하며 조건을 만족한는 값을 찾습니다.
  • 조건은 그 값으로 랜선들을 절단 한 후에 절단한 랜선들의 개수 합이 N보다 같거나 커야 합니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const getSum = (arr, K, len) => {
	let sum = 0;
	for (let i = 0; i < K; i++) {
		sum += parseInt(arr[i] / len);
	}

	return sum;
};

const solution = (input) => {
	const [K, N] = input[0].split(" ").map(Number);
	const arr = input
		.slice(1, K + 1)
		.map(Number)
		.sort((a, b) => a - b);

	let res = 1;
	let low = 1;
	let high = arr[K - 1];
	while (low <= high) {
		const mid = parseInt((low + high) / 2);

		if (getSum(arr, K, mid) >= N) {
			res = mid;
			low = mid + 1;
		} else high = mid - 1;
	}

	console.log(res);
};

solution(input);

후기

  • 이번 문제도 단순히 배열안에서 어떤 값의 존재 여부를 찾기보다는 특정 범위에서 어떤 조건을 만족하는 수를 찾는 이진 탐색 문제였습니다.
  • 문제의 조건을 대충 읽고 범위를 0부터 라고 지정했다가 틀렸었습니다. 문제의 범위는 자연수였습니다.