[JavaScript] 백준 1654 랜선 자르기

태그

이분 탐색

매개 변수 탐색

생성일

2025/04/14 10:01

URL

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

문제 설명

•

길이가 제각각인 KKK개의 랜선을 잘라서 같은 길이의 랜선 NNN개를 만들 수 있는 최대 길이를 구하는 문제

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

•

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

제약 조건

•

1≤K≤10,0001 ≤ K ≤ 10,0001≤K≤10,000

•

1≤N≤1,000,0001 ≤ N ≤ 1,000,0001≤N≤1,000,000

•

K≤NK ≤ NK≤N

•

0<0 <0< 랜선의 길이 ≤231−1≤ 2^{31}-1≤231−1

문제 풀이

접근1 브루트 포스 - 상한 O(231)O(2^{31})O(231)

•

접근2 완전 탐색 - 상한 O(K⋅log 231)O(K \cdot log \ 2^{31})O(K⋅log 231)

◦

만들 수 있는 랜선의 길이의 최댓값을 구해야 하므로, 가능한 길이의 범위를 기준으로 이진 탐색을 수행

▪

어떤 길이 L로 잘랐을 때 만들 수 있는 랜선의 개수가 N개 이상 → 더 긴 길이도 가능한지 탐색

▪

반대로 N개 미만이면 → 길이를 줄여야 함

◦

이진 탐색 대상

▪

최소: 1

▪

최대: 입력값으로 주어진 배열에서 가장 긴 랜선 길이

let left = 1;
let right = Math.max(...cables); // 가장 긴 랜선 길이
let answer = 0;
JavaScript
복사

◦

이진 탐색

while (left <= right) {
  let mid = Math.floor((left + right) / 2);

  let count = 0;
  for (let len of cables) {
    count += Math.floor(len / mid); // mid 길이로 잘랐을 때 몇 개 나오는지
  }

  if (count >= N) {
    // 더 긴 길이도 가능한지 탐색
    answer = mid;
    left = mid + 1;
  } else {
    // 너무 길어서 N개 못 만듦 → 줄이기
    right = mid - 1;
  }
}
JavaScript
복사

◦

결과 출력

console.log(answer); // 가장 마지막으로 저장된 mid 길이 값 출력 = 최대 길이
JavaScript
복사

풀이 코드

처음에 제출한 코드

•

접근2 완전 탐색 - 상한 O(K⋅log 231)O(K \cdot log \ 2^{31})O(K⋅log 231)

const fs = require('fs');

const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const [K, N] = input[0].split(' ').map(Number);
const cables = input.slice(1).map(Number);

let left = 1;
let right = Math.max(...cables);
let answer = 0;

while (left <= right) {
  const mid = Math.floor((left + right) / 2);
  const count = cables.reduce((sum, len) => sum + Math.floor(len / mid), 0);

  if (count >= N) {
    answer = mid;      // 길이 가능한 경우, 최댓값 갱신
    left = mid + 1;    // 더 길게 잘라도 가능한지 확인
  } else {
    right = mid - 1;   // 너무 많이 잘라서 N개 안 됨 → 길이 줄이기
  }
}

console.log(answer);
JavaScript
복사