[백준 15810] 풍선 공장

www.acmicpc.net/problem/15810

15810번: 풍선 공장

이분탐색을 사용하여 조건에 맞는 최솟값을 리턴하는 문제이다.

최소 시간을 리턴해야하므로 b=m이어도 end를 최대한 줄여야 한다.

b< m인 경우 mid가 조건에 만족하지 않는, 즉 정답값이 아니므로 start는 mid+1에서 시작한다.

 

마지막에 리턴하는 값은 end값으로 end연산할때마다 최솟값을 업데이트하는 방법으로 계산해도 된다.

 

++ 추가코드

long long a = b*c (b와 c는 int)

제대로 된 값이 안나온다 ^^! 왜냐면 b*c가 이미 오버플로우라서..ㅎㅎ 1LL을 곱해주도록 하자.

#include <stdio.h>

using namespace std;
int n, m;
int arr[1000000];
int maxVal = -1;
int main(void)
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
    maxVal = arr[i] > maxVal ? arr[i] : maxVal;
  }
  long long start = 1, end = 1LL*maxVal*m;
  long long b;
  while (start + 1 < end)
  {
    b = 0;
    long long mid = start + (end - start) / 2;
    for (int i = 0; i < n; i++)
    {
      b += mid / arr[i];
    }

    if (b >= m)
    {
      end = mid;
    }
    else
    {
      start = mid;
    }
  }

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

 

 

 

#include <stdio.h>

using namespace std;
int n, m;
int arr[1000000];
int main(void)
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  long long start = 1, end = 1000000000001;
  long long b;
  while (start < end)
  {
    b = 0;
    long long mid = start + (end - start) / 2;
    for (int i = 0; i < n; i++)
    {
      b += mid / arr[i];
    }

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

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