글 읽기 - 이분탐색 이해 질문

nill1024 5년 전 1

정말 이 문제에서 이해가 안되는 부분이 있는데,,,

47번 줄에 보시면 end = mid-1 이라고 되어있는 부분이 있습니다.

이 부분을 end = mid;로 고치면 문제가 맞았습니다로 뜨는데

저는 아무리 생각해봐도 이해가 되지 않습니다.

end = mid-1; 일때도 정답이 되는게 정상 아닌가요?

초고수님들의 답변 부탁드립니다. 반례도 좋습니다.

#include<cstdio>
#include<malloc.h>

using namespace std;

typedef long long int lld;

lld N, M;
lld ans;

lld cuttingsum(lld cuttingheight, lld *array)
{
    lld sum =0;
    for(lld i =0;i<N;i++)
        if(cuttingheight<array[i])
            sum += array[i] - cuttingheight;
        
    return sum; 
}

int main(void)
{
	scanf("%lld%lld",&N,&M);

    lld heightest = 0;

	lld *A = (lld*)malloc(N * sizeof(lld));
    lld *array = A;

    for(int i =0;i<N;i++)
    {
        scanf("%lld", A+i);
        if(A[i] > heightest)
            heightest = A[i];
    }
 
    lld start, end;
    start = 0;
    end = heightest;

    while(start<end){
        lld mid = (start + end) /2;
        lld sum = cuttingsum(mid, array);

        if(sum < M){
            end = mid-1; // 이게 왜 mid-1이 아닌 mid여야 하는가?
        }
        else if(sum > M){
            ans = mid;
            start = mid+1;
        }
        else
        {
            ans = mid;
            break;
        }
    }
    printf("%lld", ans);
    return 0;
}

djm03178 5년 전 2

41번째 줄의 조건 때문에 start == end가 되었을 때 cuttingsum(start, array)를 검사하지 않으므로 답이 이 지점에 있는 경우를 놓치게 됩니다.

예를 들면 아래와 같은 예시가 반례가 됩니다.

2 6
8 8

nill1024 5년 전 1

갓님,, 감사합니다

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

문제

문제

출처

ICPC

이분탐색 이해 질문

nill1024 5년 전 1

djm03178 5년 전 2

nill1024 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말