글 읽기 - 반례 하나만 제시해 주세요...ㅠㅠ

kevinshin123 4년 전 0

이분탐색으로 문제를 풀었습니다. 이대로 제출하면 '틀렸습니다.'가 뜨는 것으로 봐서 당연히 반례가 있는 것 같습니다. 반례를 하나만 제시해 주시고 왜 이렇게 풀면 틀리는지도 설명해 주시면 감사하겠습니다.

저는 while문 안에서

if (sum < m)

right = mid - 1;

else

left = mid + 1;

이 파트가 문제일 거라는 감이 오는데 왜 문제가 되는 건가요?

#include <stdio.h>

int tree[1000000];

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", tree + i);

	int left = 0;
	int right = 1000000000;    //나무 높이 Max
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		long long sum = 0;
		for (int i = 0; i < n; i++)
			if (tree[i] > mid)
				sum += tree[i] - mid;
		if (sum < m)
			right = mid - 1;
		else
			left = mid + 1;
	}
	printf("%d", mid);

	return 0;
}

djm03178 4년 전 5

2 3

2 2

탐색을 끝냈을 때의 mid가 정답이 되지 않을 수도 있습니다. 이 코드의 경우 left = 0, right = 1인 상태를 거치게 되는데, 여기서 mid = 0이 되면서 sum = 4가 되고 이 때문에 left = 1, right = 1, mid = 1로 다시 한 번 탐색을 거치게 됩니다.

kevinshin123 4년 전 0

아 감사합니다!!

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

문제

문제

출처

ICPC

반례 하나만 제시해 주세요...ㅠㅠ

kevinshin123 4년 전 0

djm03178 4년 전 5

kevinshin123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말