문제

[백준] 서버실

접근방법

시간제한을 통과하기 위해 이분탐색을 사용한다

들어오는 컴퓨터의 수를 하나의 배열에 넣고 큰 수대로 sort를 한다

이분탐색을 통해 중간의 수를 고른다

중간수 * 주간수의 idx를 곱하고
자신 뒤에 있는 수는 더한다
이렇게 자신의 층일 때 컴퓨터의 갯수를 찾는다

비교하여 start와 end값을 옮겨 범위를 수정해간다

타겟보다 합이 크면 리턴한다

다시보니 논리가 복잡하고 틀릴 수 있는 부분이 보인다

1. 중간값을 골랐을 때 자기의 앞뒤로 자기와 똑같은 수를 가지는 경우가 발생한다
   이 경우에 해당 층의 최대값을 가지고 오지 못한다

이를 수정해서 다시 작성해보자

실패코드

#include <bits/stdc++.h>
using namespace std;

int coms[1000000] = { 0 };

int binarySearch(double target, int len) {
	int st = 0;
	int en = len - 1;
	int sum = 0;
	while (st <= en) {
		sum = 0;
		int mid = (st + en) / 2;

		for (int i = mid; i < len; i++) sum += coms[i];
		sum += mid * coms[mid];

		if		(sum <  target) { en = mid - 1; } // 범위증가
		else if (sum >  target) { st = mid + 1; } // 범위감소
		else if (sum == target) { return mid; }
	}
	if (sum > target) return st;
	else return st - 1;
}

int main(void) {
	int N; cin >> N;
	int cCount = 0;

	for (int i = 0; i < N * N; i++) {
		cin >> coms[i];
		cCount += coms[i];
	}

	sort(coms, coms + N * N, greater<int>());
	if (cCount == 0) { cout << 0; }
	else cout << coms[binarySearch((double)cCount/2, N * N)];

}