글 읽기 - C언어 답을 맞추었지만 궁금한 부분이 있어 질문드립니다.

kmhwa09 3년 전 0

제가 정렬을 며칠전에 공부했었어서 이용했던 것들을 되짚어보려고 풀어보려고하였습니다.

그래서 이분탐색(명칭이 맞는지 모르겠습니다.) 구하는 과정에서 중간값(코드에서는 pivot입니다)을 (최소값+최댓값)/2 로 알고있었기때문에 앞서 언급한대로 풀려고 했지만 while문 안에서 무한반복이 되는 현상이 발생하였습니다.

질문게시판을 돌아다니다 (최솟값+최댓값+1)/2 로 푸신분을 찾았어서 수정해서 풀었더니 맞았습니다.

어째서 +1의 차이로 갈린것인지 고민하던 중, 뭔가 알듯말듯하지만 명확히 설명을 못하겠는 상황이어서 질문을 드립니다.. 아래 코드 첨부하겠습니다.

#include <stdio.h>

long long Max(long long a, long long b)
{
	return (a>b ? a : b);
}

long long val[1000001];

int main(void) {
	long long m,n;
	long long max=0;
	scanf("%lld %lld",&n,&m);
	for(long long i=0;i<n;i++){
		scanf("%lld",&val[i]);
		max = Max(max,val[i]);
	}
	long long min=0, sum, pivot;
	while (min<max){
		sum=0;
		pivot = (min + max+1)/2;
		for(long long i=0;i<n;i++){
			sum += Max(val[i]-pivot,0);
		}
		if(sum<m)
			max = pivot -1;
		else
			min = pivot;
	}
	printf("%lld\n", min);

	return 0;
}

cocoon 3년 전 0

28번줄에 min = pivot + 1로 설정해야 루프를돌면서 min > max가 되고 루프를 탈출하게 됩니다.

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

문제

문제

출처

ICPC

C언어 답을 맞추었지만 궁금한 부분이 있어 질문드립니다.

kmhwa09 3년 전 0

cocoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말