글 읽기 - 이진 탐색으로 풀려고 하는데 잘 안되네요

jaekuky 4년 전 0

이진 탐색으로 풀려고 하는데 잘 안되네요

확인해 보시고 어디가 잘못됬는지 알려주시면 감사하겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int check(int *trees, int N, int M, int H) {
	int result;
	int sum = 0;

	for (int i = 0; i < N; i++) {
		if (trees[i] > H) {
			sum += trees[i] - H;
		}	
	}

	if (sum < M) {
		result = 1;
	}
	else if (sum > M) {
		result = 2;
	}
	else {
		result = 3;
	}

	return result;
}

int main()
{
	int N, M, H;
	int start, end, mid, result;
	int *trees;
	bool flag = false;

	scanf("%d %d", &N, &M);

	trees = (int *)calloc(N, sizeof(int));

	for (int i = 0; i < N; i++) {
		scanf("%d", &trees[i]);
	}

	sort(trees, trees + N);

	start = trees[N - 1];
	end = 0;
	mid = (start + end) / 2;

	while ((start + 1) > end) {
		result = check(trees, N, M, mid);

		if (result == 1) {
			start = mid - 1;
		}
		else if (result == 2) {
			end = mid + 1;
		}
		else if (result == 3) {
			flag = true;
			break;
		}


		mid = (start + end) / 2;
	}

	if (flag == true) {
		H = mid;
	}
	else
	{
		H = start;
	}
	
	printf("%d\n", H);

	free(trees);

    return 0;
}

oree2113 4년 전 1

sum 을 계산하는 과정에서 Integer의 범위를 넘어갈 수 있습니다.

jaekuky 4년 전 0

감사합니다

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

문제

문제

출처

ICPC

이진 탐색으로 풀려고 하는데 잘 안되네요

jaekuky 4년 전 0

oree2113 4년 전 1

jaekuky 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말