개발자 톡
두 코드의 차이가 뭔지 모르겠습니다.
- 등록일
- 2024-08-22 17:38:02
- 조회수
- 93
- 작성자
- hm02123
A 코드와 B 코드의 차이는 cal 함수의 return false가 for문의 안에 있는 것과 밖에 있는 차이 뿐입니다.
return false가 for문 안에 있는 A코드는 정답이 맞으며 return false가 for문 밖에 있는 B 코드는 오답이 발생합니다. (시간 초과가 아닌 그냥 오답입니다.)
왜 이런 차이가 발생하는지 모르겠습니다.
A 코드)
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
int n;
ll arr[100001];
ll b;
bool cal(ll k) {
ll mini = arr[0] + k;
ll sum = 0;
if (k == 0) return true;
for (int i = 0; i < n; i++) {
if (arr[i] < mini)
sum += (ll)pow(mini - arr[i], 2);
else
break;
if (sum > b) return false;
}
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> b;
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
ll st = 0;
ll en = (ll)sqrt(b);
while (st < en) {
ll mid = (st + en + 1) / 2;
if (cal(mid)) // 총합이 b보다 작거나 같음
st = mid;
else
en = mid - 1;
}
cout << arr[0] + st;
return 0;
}
B 코드)
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
int n;
ll arr[100001];
ll b;
bool cal(ll k) {
ll mini = arr[0] + k;
ll sum = 0;
if (k == 0) return true;
for (int i = 0; i < n; i++) {
if (arr[i] < mini)
sum += (ll)pow(mini - arr[i], 2);
else
break;
}
if (sum > b) return false;
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> b;
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
ll st = 0;
ll en = (ll)sqrt(b);
while (st < en) {
ll mid = (st + en + 1) / 2;
if (cal(mid)) // 총합이 b보다 작거나 같음
st = mid;
else
en = mid - 1;
}
cout << arr[0] + st;
return 0;
}