[JS/C++][백준]16401_과자 나눠주기

문제 번호

16401번: 과자 나눠주기

 

 

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

 

문제 풀이

 이분탐색을 통하여 '조카들에게 나눠줄 과자의 길이'를 찾으면 된다.

풀이에 이용되는 숫자들은 모두 int 범위에 해당된다.

 

 left를 0, right를 1000,000,000으로 두고 이분탐색을 시작하여 과자의 길이를 찾아나선다.

매번 mid를 과자의 길이로 하여서 check라는 함수를 통하여 mid라는 길이만큼 과자들을 조카들에게 나누어 줄 수 있는지 확인한다. 

 check 함수는 문제에서 주어진 과자들의 목록을 mid로 나누어서 몫을 더해본다. 이때 몫들의 합이 조카들의 수인 M 이상 이라면 해당 길이만큼은 조카들에게 과자를 줄 수 있다.

 만약 check 함수를 통과하지 못한다면 mid라는 길이만큼은 조카들에게 줄 수 없다. 따라서 좀더 짧은 길이의 과자길이를 찾아보아야 한다.

 

JS 풀이

function check(M, snak, ans) {
  let cnt = 0;
  for (let i = 0; i < snak.length; i++) {
    cnt += Math.floor(snak[i] / ans);
  }
  if (cnt >= M)
    return true;
  return false;
}

function binarySearch(M, snak) {
  let answer = 0;

  let left = 1;
  let right = 1000000000;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (check(M, snak, mid)) {
      left = mid + 1;
      answer = mid;
    }
    else {
      right = mid - 1;
    }
  }

  return answer;
}

function sol(M, snak) {
  snak.sort(( a, b ) => a - b);
  console.log(binarySearch(M, snak));
}

function insert() {
  const input = require('fs').readFileSync('과자 나눠주기2/input.txt').toString().split('\n');
  const [M, N] = input[0].split(' ').map(Number);
  const snak = input[1].split(' ').map(Number);  
  sol(M, snak);
}
insert();

 

C++ 풀이

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool check(int M, vector<int> snak, int ans){
  int cnt = 0;
  for(int i=0; i<snak.size(); i++){
    cnt += snak[i]/ans;
  }
  if(cnt >= M)
    return true;
  return false;
}

int binarySearch(int M, vector<int> snak){
  int answer = 0;

  int left = 1;
  int right = 1000000000;

  while( left <= right){
    int mid = (left+right) / 2;

    if(check(M,snak,mid)){
      left = mid + 1;
      answer = mid;
    }
    else {
      right = mid - 1;      
    }
  }
  return answer;
}

void sol(int M, vector<int> snak){
  sort(snak.begin(), snak.end());
  cout << binarySearch(M,snak);
}

int main(){
 int M , N; cin >> M >> N;
 vector<int> snak;
 for(int i=0; i< N; i++){
   int num;
   cin >> num;
  snak.push_back(num);
 }

 sol(M,snak);
}

 

특이사항