[JS][백준]17179_케이크 자르기

문제 번호

17179번: 케이크 자르기

 

 

 

알고리즘 분류

이분 탐색, 그리디

 

문제 풀이

 이분 탐색을 사용해서 '가장 작은 케이크의 길이'를 '최대'로 만드는 문제이다. 케이크를 자르면 가장 작은애가 나오게 될텐데 걔의 길이를 가능한 길게 하라는 말이다. 

 여기서 이분 탐색은 '가장 작은 케이크의 길이'를 찾는데 사용된다. 왜 이분 탐색을 사용하는지 생각해보면 '가장 작은 케이크의 길이'가 '최대'일때를 구하려면 케이크를 자를 때 마다 가능한 중앙에서 가까운 부분을 잘라야한다.

 

cake 배열의 마지막에 케이크의 전체 길이를 넣어준다. 이분탐색에 사용하기 위해서이다.

for(let i=0; i<cake.length-1; i++){
  let temp = Number(input.shift());
  cake[i] = temp;
}
cake[M] = L;

 

 '가장 작은 케이크의 길이' 를 mid 라고하자. 이때 mid는 (0+L)/2 이다. 

function sol(q){
  let answer = 0;
  let start = 0;
  let end = L;  

  while(start<=end){
    let mid = parseInt((start+end)/2);

    if(check(mid,q)){
      answer = answer > mid ? answer : mid;
      start = mid+1;
    }
    else{
      end = mid-1;
    }
  }

  return answer;
}

 

 '가장 작은' 케이크의 길이가 mid 이므로 mid 보다 작은 길이의 케이크는 존재하지않는다. 즉 모든 케이크의 길이는 mid 이상이라는 뜻이다. 이걸 기억하고 check(mid,q) 함수를 작성한다.

 if(cake[i] - prev >= mid) : 케이크를 잘랐을때 조각이 mid 보다 길면 케이크를 자른다. 그리고 prev = cake[i]를 통해서 자른 지점을 기억한다. 

 자를 수 있는 모든 구간을 확인했을때 주어진 횟수이상 잘렸다면 mid의 길이가 정답이거나 더 길어질 수 있다.

p<0 인 이유는 q번 잘랐을때 마지막 남은 조각의 길이도 mid 이상이여야 하기 때문이다. q<=0 으로 하면 마지막 남은 조각의 길이를 확인하지 않는다.

function check(mid,q){
  let prev = 0;
  for(let i=0; i<cake.length; i++){
    if(cake[i] - prev >= mid){
      q--;
      prev = cake[i];
    }
  }

  return q < 0 ? true : false;
}

 

 check 가 'false'라면 mid 의 길이가 너무 길다는 뜻이다. 즉 '가장 작은 케이크의 길이' 를 줄여야한다. 

반대로 'true'라면 mid 의 길이를 늘려서 다시 시도해볼 수 있다.

 

전체코드

const fs = require('fs');
const input = fs.readFileSync('케이크 자르기/input.txt').toString().trim().split('\n');

const NML = input.shift().split(' ');
const N = Number(NML[0]);
const M = Number(NML[1]);
const L = Number(NML[2]);
let cake = new Array(M+1);
for(let i=0; i<cake.length-1; i++){
  let temp = Number(input.shift());
  cake[i] = temp;
}
cake[M] = L;
let testCase = new Array(N);
for(let i=0; i<testCase.length; i++){
  testCase[i] = Number(input.shift());
}

function check(mid,q){
  let prev = 0;
  for(let i=0; i<cake.length; i++){
    if(cake[i] - prev >= mid){
      q--;
      prev = cake[i];
    }
  }

  return q < 0 ? true : false;
}


function sol(q){
  let answer = 0;
  let start = 0;
  let end = L;  

  while(start<=end){
    let mid = parseInt((start+end)/2);

    if(check(mid,q)){
      answer = answer > mid ? answer : mid;
      start = mid+1;
    }
    else{
      end = mid-1;
    }
  }

  return answer;
}

for(let i=0; i<testCase.length; i++){
  let q = testCase[i];
  //console.log(q);
  console.log(sol(q));
}

 

 

 

특이사항

 이분 탐색의 개념은 알고있었지만 문제로 만나본건 많지 않아서 다른분들의 풀이를 보고 공부했다. 

이분 탐색으로 '무엇을' 찾을것인가를 정확하게 정해야한다. 이분 탐색시 이 문제처럼 '값'을 사용할것인지, '인덱스'를 사용할것인지도 잘 판단해야한다. 그리고 이분 탐색 문제들은 이분 탐색 + '문제의 요구사항' 의 형태로 나오는 것 같다.