[백준 3079] 입국심사

www.acmicpc.net/problem/3079

3079번: 입국심사

이제 이분탐색을 사용하는 문제에 얼추 감이 오는 듯하다. 그치만 막상 코테에서 보면 어버버하겠지..?ㅎ

 

이분탐색을 사용하는 문제이다. 조건을 만족하는 최소 시간을 구하는 문제로 풍선공장이랑 푸는 방법이 같다.

start와 end를 설정하고 mid를 확인하여 mid 시간안에 심사받는 인원이 주어진 인원수 m보다 크거나 같다면 최소 시간이 필요하므로 end를 축소시킨다.

반대로 m보다 작다면 start를 늘려서 범위를 재조정한다.

 

#include <stdio.h>

using namespace std;

int n;
long long m;
long long mem;
int arr[100000];
int main(void)
{
  scanf("%d%lld", &n, &m);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  long long start = 1, end = arr[0] * m;

  while (start < end)
  {
    long long mid = (start + end) / 2;
    mem = 0;
    for (int i = 0; i < n; i++)
    {
      mem += mid / arr[i];
    }

    if (mem >= m)
    {
      end = mid;
    }
    else
    {
      start = mid + 1;
    }
  }

  printf("%lld\n", end);
  return 0;
}