scared22   1년 전

제가 모든 부분에 케이스에 대해서 적용을 해보진 못했지만 왠만한 경우는 다된다고 생각을 합니다.

어떤 경우에서 이답이 오답이 나오는지 모르겠습니다.

ㅜㅜ 이문제에서 벗어나고 싶습니다. 도와주세요 ㅜㅜ

pichulia   1년 전

지금 현재

2 5

9 10

데이터를 넣으면

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


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


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

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

kyma123   1년 전

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

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

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

kyma123   1년 전

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

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

yukariko   1년 전

kyma123

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

1 1000000000

1000000000

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

1000000000 실제 가능한 범위

1048576 배열로 선언한 범위

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

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

kyma123   1년 전

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

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

scared22   1년 전


#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;
}

다시 변경을 해봤는데 오답이 뜨네요 어혀 ;; 전 바보인가 봅니다 .

pichulia   1년 전

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

scared22   1년 전

결국 그것도 문제 였지만

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

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

댓글을 작성하려면 로그인해야 합니다.