백준_케이크 자르기_17179

케이크 자르기

문제

생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다.

예를 들어 70cm의 롤 케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자. 만약 목록에 적힌 수 중 하나가 3이라면 이때 가장 작은 조각의 길이는 최대 15cm이다. 예를 들어 20cm, 35cm, 55cm 지점을 자를 때 최대가 된다.

입력

첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000)

다음 M줄에 걸쳐 자를 수 있는 지점을 나타내는 정수 Si가 주어진다. (1 ≤ Si < L)

다음 N줄에 걸쳐 자르는 횟수를 나타내는 정수 Qi가 주어진다. (1 ≤ Qi ≤ M)

Si는 오름차순으로 주어지고 중복되는 수는 없으며, Qi도 마찬가지이다.

출력

N개 줄에 걸쳐 각 목록에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이의 최댓값을 출력한다.

예제 입력

2 5 70
10
20
35
55
60
3
4

예제 출력

15
10

Code

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

// N: 자르는 횟수가 담긴 목록의 길이, M: 자를 수 있는 지점의 개수, L: 롤케이크 길이
const [N, M, L] = input[0].split(' ').map(Number);
const S = []; // 자를 수 있는 지점
for (let i = 1; i <= M; i += 1) S.push(+input[i]);
S.push(L); // 마지막으로 롤케이크 끝 길이 담기
const Q = []; // 자르는 횟수
for (let i = 1 + M; i < 1 + M + N; i += 1) Q.push(+input[i]);

// 최소 길이 설정했을 때, Ni횟수만큼 케이크를 자를 수 있는지 확인하는 함수
const isPossibleCut = (minLen, count) => {
  let prevCm = 0; // 직전에 케이크 자른 위치
  S.forEach((s) => {
    // 최소 길이보다 케이크를 크거나 같게 자를 수 있는 경우, 자르기
    if (s - prevCm >= minLen) {
      count -= 1;
      prevCm = s;
    }
  });
  return count < 0; // 케이크 자를 수 있는지 리턴
};

let result = '';
Q.forEach((q) => {
  let maxLen = 0; // 가장 작은 조각의 길이 최대값
  let [left, right] = [1, L];
  while (left <= right) {
    const mid = parseInt((left + right) / 2); // mid: 작은 조각의 길이
    // 자를 수 있다면, 최대값 갱신해주고 작은 조각의 길이 늘리기
    if (isPossibleCut(mid, q)) {
      maxLen = Math.max(mid, maxLen);
      left = mid + 1;
    } else right = mid - 1; // 자를 수 없다면, 작은 조각 길이가 크므로 조각 길이 줄이기
  }
  result += maxLen + '\n';
});

result = result.trimEnd();
console.log(result);

풀이 및 해설

• 케이크를 자를 때 가장 작은 케이크 조각의 길이 구하기
  • M: 자를 수 있는 구간 개수, N: 자르는 횟수가 담긴 목록의 길이, L: 롤케이크의 길이
• 위 예시) 3번 자를 때, 나올 수 있는 가장 작은 케이크 조각의 최댓값 ⇒ 15cm(20, 35, 55 구간 자름)

• 이분 탐색 풀이
  • target ⇒ 가장 작은 케이크 조각의 길이[1(자를 수 잇는 지점이 1이상 L미만이므로 0이 될 수는 없음)~케이크 길이]
  • target을 설정했을 때 N 목록에 있는 횟수 만큼 자를 수 있는지 확인하며 이분탐색 진행
  • N목록에 있는 횟수 만큼 자를 수 있는지 확인
    • 케이크 자를 수 있는 구간들을 순회하며 target 길이보다 크거나 같을 경우만 자를 수 있음
  • 자를 수 있다면, 최대 길이 업데이트 및 target 늘리기(left를 mid+1값으로 이동) ⇒ 최대값을 구하기 위해서
  • 자를 수 없다면, target이 너무 크다는 뜻 ⇒ target 줄이기(right를 mid-1값으로 이동)