지금 현재

2 5

9 10

데이터를 넣으면

답이 5가 출력되고 있습니다.

일단 이진탐색에서 while문 끝나고 난 다음의 코드가 총체적 난국이니 이부분부터 빠르게 고칩시다.

그리고 문제조건에 의하면 sum값이 int범위를 넘어가도록 들어올 수도 있기 때문에

변수 타입을 long long으로 바꾸셔야 합니다...

사실 굳이 바이너리 서치까지 거창하게 끌어들일 필요 없는 간단하고 이해도 쉬운 방법도 있습니다.

현재 세팅된 값이 m+1일 때, m으로 세팅을 바꾸면 추가적으로 잘리는 나무의 길이가 m보다 큰 나무의 갯수의 합과 같다는 점을 이용하면 간단히 풀 수 있습니다.

m에 가장 큰 나무의 크기를 넣어주고, m에서 1씩 빼가며 m보다 큰 나무의 갯수를 x에 저장하고, 매 과정마다 x를 총합 sum에다 더해주면서 sum이 l보다 커지는 순간 break 해주면 됩니다.

아, l은 우리가 잘라야 할 최소 길이, 즉 입력값입니다.

또한 이럴 경우 sum이 l의 두 배 보다 항상 작을 수 밖에 없으므로 굳이 64비트로 선언하지 않아도 되는 이점이 있습니다.

@kyma123

kyma님이 제출하신 소스를 읽어보았는데 입력이 아래와 같다면 시간초과를 받을것 같습니다.

1 1000000000

1000000000

그리고 배열의 크기가 1<<20 인데, 이는 입력으로 주어지는 범위에 크게 못미칩니다.

1000000000 실제 가능한 범위

1048576 배열로 선언한 범위

테스트케이스에 의해 우연히 맞은 경우로 보입니다.

따라서 맞는 소스라고 보기는 힘들겠지요..

엇 다시 보니 높이가 10⁹ 까지었군요... N만 보고 높이 역시 그러할 것이라고 착각했네요 으악=_=;;;;

근데 정답인 걸 봐선 데이터에 문제가 있는 게 맞는 것 같네요

#include <iostream>
#include <algorithm>
#define Max 1000003
using namespace std;
int arr[Max],n,m;
int binary(int front, int goal, int temp)
{
int start = front, end = goal, mid;
long long int sum=0;
while (start <= end)
{
mid = (start + end)/ 2;
for (int i = 0; i < n; i++)
{
if (arr[i] - mid>0)
sum += (arr[i] - mid);
}
if (temp == sum)
return mid;
else if (temp < sum)
{
start = mid+1 ;
sum = 0;
}
else
{
end = mid - 1;
sum = 0;
}
}
for (int i = mid-1; i > 0; i--)
{
for (int j = 0; j < n; j++)
{
if (arr[j] - i>0)
sum += (arr[j] -i);
}
if (temp <= sum)
return i;
sum=0;
}
}
int main()
{
int ma=0,mi=200000001;

cin >>n>>m;

for (int i = 0; i < n; i++)
{
cin >> arr[i];
if (ma < arr[i])
ma = arr[i];
if (mi>arr[i])
mi = arr[i];
}

//정렬
sort(arr, arr + n);
//이진탐색 실시
cout<<binary(mi,ma,m)<<endl;
}

축하드려요.. sum=0; 으로 초기화 해야 한다는걸 찾아내셨군요.

결국 그것도 문제 였지만

while문을 벗어나 for문을 돌때 mid-1이 아니라 mid 부터 돌아야 정답이라는 것을 알았습니다.

ㅜㅜ 제 실력 부족입니다. 알려주셔서 감사합니다 ㅎㅎ