2805번: 나무 자르기

문제 접근 🤔

• 주어진 나무들을 자르고 남은 나무들의 길이 합이 최소한 m 이상이 되도록 하는 자르는 길이의 최댓값을 찾는 문제다.
• 이분 탐색을 이용하면 길이를 찾는 시간 복잡도를 줄일 수 있다.
• 구하는 것은 나무를 자를 길이이므로 탐색을 진행할 범위는 (0, max(trees)) 이다.
• 범위의 중간값을 mid 라 하고 mid 보다 큰 나무가 존재하면 자르고 남은 길이를 합해준다.
• 이 길이의 합이 m 과 같다면 구하는 최댓값이 현재의 mid 값이므로 저장해주고 반복문을 종료한다.
• 크다면 나무를 자를 수는 있지만 최댓값인지 모르므로 현재까지 저장된 값과 현재의 mid 중 더 큰 값을 저장하고 범위의 시작 위치를 mid 의 오른쪽으로 옮겨준다.
• 작다면 범위의 끝을 mid 의 왼쪽으로 옮겨준다.
• 이 과정이 완료되면 문제의 조건을 만족하는 최댓값을 구할 수 있다.
  
  
  

놓쳤던 부분 😅

• 없음
  
  
  

코드 😁

파이썬 코드(480 ms)

n, m = map(int, input().split())
trees = list(map(int, input().split()))
low, high = 0, max(trees)
maxLen = 0

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

    cutLen = 0
    for tLen in trees:
        if mid < tLen:
            cutLen += tLen - mid

    if m == cutLen:
        maxLen = mid
        break
    elif m < cutLen:
        maxLen = max(mid, maxLen)
        low = mid + 1
    else:
        high = mid - 1

print(maxLen)

자바스크립트 코드(1028 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 = ([n, m], trees) => {
  let [low, high] = [0, Math.max(...trees)];
  let maxLen = Number.MIN_SAFE_INTEGER;

  while (low <= high) {
    let mid = ~~((low + high) / 2);
    let cutLen = trees.reduce((sum, tLen) => (mid < tLen ? sum + tLen - mid : sum), 0);

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

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