1654번: 랜선 자르기

문제 접근 🤔

• 이 문제를 주어진 랜선들을 같은 길이로 잘라 n 개 이상으로 만들 수 있는 길이의 최댓값을 구하는 문제다.
• 이 길이를 구하기 위해 길이의 범위를 설정하자.
• 자르는 길이는 자연수이고 랜선들의 최댓값보다 커질 수 없으므로 범위는 (1, max(lanList)) 이다.
• 탐색 범위의 중간값인 mid 를 기준으로 하여 범위를 반씩 좁혀나가며 탐색을 진행한다.
• mid 로 랜선들을 자른 개수의 총합이 n 이상이면 low의 위치를 mid 의 오른쪽으로 보내주고, 자른 길이 중 최댓값을 저장한다.
• 자른 개수의 총합이 n 미만이면 high 의 위치를 mid 의 왼쪽으로 보내준다.
• 이 과정을 high가 low 보다 작아지기 전까지 반복해주면 구하는 길이의 최댓값을 구할 수 있다.
  
  
  

놓쳤던 부분 😅

• 없음
  
  
  

코드 😁

파이썬 코드(84 ms)

# 백준 입력 시간 줄이기
import sys
input = sys.stdin.readline

# 풀이 코드
k, n = map(int, input().split())
lanList = [int(input()) for _ in range(k)]
maxLen = -sys.maxsize - 1
low, high = 1, max(lanList)

while low <= high:
    mid = (low + high) // 2

    cutCnt = 0
    for lan in lanList:
        cutCnt += lan // mid

    if n <= cutCnt:
        maxLen = max(maxLen, mid)
        low = mid + 1
    else:
        high = mid - 1

print(maxLen)

자바스크립트 코드(184 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [L, ...datas] = fs.readFileSync(filePath).toString().trim().split('\n');

const solution = ([k, n], lanList) => {
  let [low, high] = [1, Math.max(...lanList)];
  let maxLen = Number.MIN_SAFE_INTEGER;

  while (low <= high) {
    let mid = ~~((low + high) / 2);
    let cutCnt = lanList.reduce((sum, lan) => sum + ~~(lan / mid), 0);

    if (n <= cutCnt) {
      maxLen = Math.max(maxLen, mid);
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  console.log(maxLen);
};

solution(L.split(' ').map(Number), datas.map(Number));