글 읽기 - 1654번 이분탐색 관련 질문드립니다. ( C++)

parkpkww 4년 전 0

이분탐색시 'Low = 1LL , High = K 개의 랜선중 최대값' 으로 놓으면 통과가 됐습니다.

그러나 High의 초기값을 랜선의 최대값인 2^31-1 으로 놓으면 답이 통과가 되지 않습니다....

고수님들 혹시 이유를 알려주실 수 있으신가요..?

통과한 코드와 그렇지 못한 코드 각각 다음과 같습니다.. ㅠ

// 통과가 되는 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, K;
ll arr[11111], ans;

int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

cin >> K >> N;
ll Low = 1LL;
ll High = 1LL;
for (int i = 0; i < K; ++i) {
	cin >> arr[i];
	High = max(High, arr[i]);
}

// 이분탐색
while (Low <= High) {
	ll mid = (Low + High) / 2;
	int temp = 0;
	for (int i = 0; i < K; ++i) 
		temp += arr[i] / mid;

	if (temp >= N) {
		ans = mid;
		Low = mid + 1;
	}
	else
		High = mid - 1;
}

cout << ans << '\n';

return 0;
}

// 통과되지 못한 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, K;
ll arr[11111], ans;

int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

cin >> K >> N;
for (int i = 0; i < K; ++i) 
	cin >> arr[i];

ll Low = 1LL;
ll High = (ll)(1<<31-1);


// 이분탐색
while (Low <= High) {
	ll mid = (Low + High) / 2;
	int temp = 0;
	for (int i = 0; i < K; ++i) 
		temp += arr[i] / mid;

	if (temp >= N) {
		ans = mid;
		Low = mid + 1;
	}
	else
		High = mid - 1;
}

cout << ans << '\n';

return 0;
}

djm03178 4년 전 0

1<<31 - 1은 연산자 우선순위에 의하여 1<<(31-1)과 같습니다. 즉, 1<<30입니다.

parkpkww 3년 전 0

와.... 그렇군요!

감사합니다!

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

문제

문제

출처

ICPC

1654번 이분탐색 관련 질문드립니다. ( C++)

parkpkww 4년 전 0

djm03178 4년 전 0

parkpkww 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말