[HSAT 4회 정기 코딩 인증평가 기출] 슈퍼컴퓨터 클러스터

https://softeer.ai/practice/info.do?idx=1&eid=1204&sw_prbl_sbms_sn=181695

 

파라메트릭 서치(매개변수 탐색) + 이분 탐색

 

1.

처음 제출했을 때, 시간 초과 발생했는데, ps() 함수 안에서 continue가 아니라 break를 했어야 했다.

continue는 의미 없다.

 

2. 

다시 시간 초과가 발생하길래 확인했더니,

++left, --right가 아니라 left = mid + 1, right = mid - 1을 했어야 했다.

실수 금지

 

시간 초과 코드 ↓

// 시간 초과 코드
#include <bits/stdc++.h>

using namespace std;

vector<long> v;
int N;
long B;

// m : 각 경우 마다, 최초 v에서 가장 낮은 성능이 올릴 수 있는 최대 성능
bool ps(long m) {

	long tmp = 0L;

	for (auto a : v) {
		if (m < a) {
			// 어차피 m보다 큰 건 올릴 수 없다.
			break; 
            // 처음 제출할 때 continue로 제출했더니 시간 초과 발생
            // 생각해보니 break가 정답
		}
		tmp += abs(m - a) * abs(m - a);
		if (tmp > B) {
			return false;
		}
	}

	return true;
}

long bt(long left, long right) {

	long ret = 0L;

	while (left <= right) {
		long mid = (left + right) >> 1L;
		if (ps(mid)) {
			// mid가 가능하므로, 최댓값을 구하기 위해 가능한 경우를 최대한 올려서 탐색
			++left;
		}
		else {
			--right;
		}
	}

	return right;
}

int main(int argc, char** argv)
{
	long input;

	scanf("%d %ld", &N, &B);

	for (int i = 0; i < N; i++) {
		scanf("%ld", &input);
		v.push_back(input);
	}

	sort(v.begin(), v.end());

	long left = v[0];
	long right = v[N - 1] + sqrt(B);

	printf("%ld\n", bt(left, right));

	return 0;
}

 

정답 코드 ↓

#include <bits/stdc++.h>

using namespace std;

vector<long long> v;
int N;
long long B;

// m : 각 경우 마다, v에서 가장 낮은 성능이 올릴 수 있는 최대 성능
bool ps(long long m) {

	long long tmp = 0L;

	for (auto a : v) {
		if (m < a) {
			// 어차피 m보다 큰 건 올릴 수 없다.
			break;
		}
		tmp += (m - a) * (m - a);
		if (tmp > B) {
			return false;
		}
	}

	return true;
}

long long bt(long long left, long long right) {

	while (left <= right) {
		long long mid = (left + right) >> 1L;

		if (ps(mid)) {
			// mid가 가능하므로, 최댓값(mid)을 구하기 위해 가능한 경우를 최대한 올려서 탐색
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	return right;
}

int main(int argc, char** argv)
{
	long long input;

	scanf("%d %lld", &N, &B);

	for (int i = 0; i < N; i++) {
		scanf("%lld", &input);
		v.push_back(input);
	}

	sort(v.begin(), v.end());

	long long left = v[0];
	long long right = v[N - 1] + sqrt(B);

	printf("%lld\n", bt(left, right));

	return 0;
}