[JS][백준]14627_파닭파닭

문제 번호

14627번: 파닭파닭

 

 

 

알고리즘 분류

• 이분 탐색

 

문제 풀이

 문제의 알고리즘은 어렵지 않은 이분 탐색이다.

처음엔 주어진 파들을 무조건 사용해야 하는줄 알고 이분탐색의 최대 범위를 가장 짧은 파의 길이로 두고 했다가 틀렸었다.

그런데 수의 범위가 크기 때문에 BigInt를 사용해야 한다. 이때 BigInt의 연산 시간은 상수 시간이 아니므로 무분별하게 BigInt를 사용한다면 같은 알고리즘 이더라도 시간 초과에 걸리게 된다.

 때문에 BigInt를 꼭 필요한 곳에 잘 사용해줘야 한다.

파의 길이가 최대 1,000,000,000이라고 하였으므로 left를 1로, right를 파 길이의 최댓값으로 두고 이분 탐색을 진행한다.

function binarySearch() {
   let ret = 0n;
 
   let left = 1n;
   let right = 1000000000n;
   while (left <= right) {
     let mid = BigInt(parseInt((left + right) / 2n));
     if (check(mid)) {
       left = mid + 1n;
       ret = mid;
     } else {
       right = mid - 1n;
     }
   }
 
   return ret;
 }

 

 mid 값에 대해서 check 함수의 값을 확인한다. 각 파의 길이에 따라서 파닭에 필요한 파를 몇 덩이 얻을 수 있는지 계산한다.

function check(key) {  // key의 최대값 10^9.
   let ret = 0;
 
   for (let i = 0; i < pa.length; i++) { // 최대 10^6개.
     ret += parseInt(pa[i] / BigInt(key));  // 파의 최대 길이 10^9.
   }
 
   if (ret >= C) return true;
   else return false;
 }

 

 이렇게 계산하고 모든 파 길이의 합(total)에서 (파닭에 넣을 수 있는 파의 최대길이 * 필요한 파닭의 수 )를 빼주면 된다.

 

전체 코드

/**
 * 가장 짧은 길이의 파의 길이에 대해서 이분탐색으로 파닭에 넣을 파의 양을 결정한다.
 */
 const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
 let [S, C] = input[0].split(' ').map(Number);
 C = BigInt(C)
 let pa = input.slice(1).map(_ => _.trim()).map(BigInt);
 
 function check(key) {  // key의 최대값 10^9.
   let ret = 0;
 
   for (let i = 0; i < pa.length; i++) { // 최대 10^6개.
     ret += parseInt(pa[i] / BigInt(key));  // 파의 최대 길이 10^9.
   }
 
   if (ret >= C) return true;
   else return false;
 }
 function binarySearch() {  // 연산 과정에서 나올 수 있는 최대 수 2*10^9.
   let ret = 0n;
 
   let left = 1n;
   let right = 1000000000n;
   while (left <= right) {
     let mid = BigInt(parseInt((left + right) / 2n));
     if (check(mid)) {
       left = mid + 1n;
       ret = mid;
     } else {
       right = mid - 1n;
     }
   }
 
   return ret;
 }
 function sol() {
   let answer = 0n;
 
   let longgestPa = binarySearch();  // 주어진 파 중에 길이가 가장 짧은 파. 
   let total = 0n;
   for (let i = 0; i < pa.length; i++) {
     total += pa[i];
   }
 
   return console.log((total - longgestPa * C).toString().trim());
 }
 sol();

특이사항

BigInt의 연산 시간은 상수 시간이 아니다. 따라서 같은 알고리즘이더라도 시간 초과를 초래할 수 있다.