백준 2417 - 정수 제곱근 (이분탐색 완전 정복하기)

https://www.acmicpc.net/problem/2417

2417번: 정수 제곱근

그냥 sqrt를 써도 될 거 같긴 한데, 문제가 원하는 대로 이분탐색을 이용해 풀자.

 

이분탐색의 일반적 풀이. 사실 이게 메인이긴 한데 문제 해설이 필요하신 분은 스킵하세요

 

이분탐색의 유형을 두 가지로 나누자면

 

1) 정확히 일치하는 값을 찾기 ex) 배열 내에 정수 3이 존재하는가?

2) 가장 근접한 값을 찾기 ex) 배열 내에서 3과의 차가 가장 작은 값은 얼마인가?

가 될 수 있겠다.

 

위 문제는 q^2 = n이라면 q가 정확히 일치하는 값이니 q를 출력하면 되고, n이 제곱수가 아니라면 가장 근접한 값(q^2 >= n인 q 중 최솟값)을 찾으면 된다.

 

정확히 일치할 경우는 그냥 반환하면 되니까 쉬운데, '가장 근접한 값'을 구현하는 법은 문제마다 조금씩 달라 매번 헷갈린다. 이러한 류의 이분탐색에서는 답의 형태를 찾고, 이에 맞게 구간 분할과 종료 조건을 신경써주면 된다.

 

먼저 구간 분할을 보자. 함수 decision(x)이 있다. decision(x)는 변수 x가 조건을 만족할 경우 참, 아닐 경우 거짓을 반환한다. 여기서는 x^2 >= n이면 참(Y), 아닐 경우 거짓(N)을 반환한다.

 

예를 들어 n = 7일 경우 1 <= x <= n인 x 값에 따른 decision(x) 값은 다음과 같다.

x	1	2	3	4	5	6	7
decision(x)	N	N	Y	Y	Y	Y	Y

n을 크게 키우면 decision의 일반적인 형태는 NNN...NNNYYY....YYYY가 된다.

여기서 우리가 찾아야 할 값은 N 이후 처음으로 Y가 등장하는 위치다.

 

답의 형태를 떠올리며 이분 탐색을 구현해보자. 매 반복마다 mid 값을 decision에 넣어본다.

decision(mid)가 N일 경우, mid와 mid 왼쪽에 위치한 모든 값은 답이 될 수 없다. 따라서 mid 오른쪽부터 이분탐색을 다시 시작한다. left = mid + 1

 

decision(mid)가 Y일 경우, mid가 첫 번째 Y이면 mid가 답이고, 그렇지 않을 경우 mid 왼쪽에 답이 있을 것이다. mid도 답이 될 수 있고 왼쪽에 답이 있을 수도 있으므로 mid를 포함해 왼쪽에서 이분탐색을 다시 시작한다. right = mid

 

종료조건은 어떻게 설정해야 할까? 일반적으로 종료조건은 무한루프를 방지하는 데 주안점을 두고 설정하면 된다. left와 right가 동일할 경우, mid가 N이면 left가 right보다 커지지만 (left = mid + 1 = right + 1), mid가 Y이면 right는 left와 동일한 값을 유지한다 (right = mid = left). 따라서 left == right일 때 반복문을 종료하지 않으면, 최악의 경우 mid가 Y일 때 무한루프가 발생하고 만다.

 

만약 left = mid + 1, right = mid - 1로 움직이는 이분탐색이 있다면 현재 left == right여도 다음 시행에서 반드시 left > right가 되므로 left == right에서 반복문을 종료할 필요가 없다.

 

종료조건 설정이 헷갈리면, 매 반복마다 left와 right를 출력해 그 실태를 확인해보고 그에 맞게 수정하자.

 

반복문을 완성했으면 고민하지 말고 left를 반환하도록 하자.

 

이 문제에서 답의 형태는 NNNNNYYYYY, 이에 따른 구간 분할은 left = mid + 1, right = mid, 이에 따른 종료조건은 left < right이다.

 

이를 바탕으로 코드를 짜면 다음과 같다.

 

#define ll long long

ll bin_search(ll n) {
	ll left = 0, right = n, mid;
    
	while (left < right) {
		mid = (left + right) / 2;
		
        //decision(x) → return (x^x >= n);
		if (decision(mid))
			left = mid + 1;
		else
			right = mid;
	}

	return left;
}