[알고리즘] 백준 2417번: 정수 제곱근 (C++), 더 큰 정수 자료형 unsigned long long

기존의 큰 정수형 자료형이 필요할 때는 long long 자료형을 사용했다.

하지만 long long을 사용하기에는 자료형이 너무 작아서 unsigned long long을 사용했다. 0보다 작을 일이 없기 때문에 가능하다.

 

그리고, 밑에 코드에서 n == 0일 때의 조건이 없을 때는 계속 98%에서 시간 초과가 났었다. 아무래도 반례를 처리하지 못하고 있는 느낌이라 n == 0일 때, 바로 0을 출력해주고 종료를 시켜주니 정답이 나왔다.

(0으로 컴파일 실험을 해보다가 0을 넣으면 무한루프가 일어나는 것을 알 수 있었다.)

---

왜 0은 무한루프를 일으켰을까 (+추가 (궁금해져서))

 

왜 0만 무한루프를 출력하는지 궁금해서 mid, low, high 순으로 while문 안에서 출력해보았다.

미해결 코드

#include <iostream>
#include <cmath>
#define ll unsigned long long
using namespace std;

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

	ll n;
	cin >> n;

	ll low = 0;
	ll high = sqrt(9223372036854776000) + 1; //2의 63 제곱
	ll answer = 0;


	while (low <= high) {
		ll mid = (low + high) / 2;

		cout << mid << ' ' << low << ' ' << high << '\n';

		ll MID = mid * mid;
		if (MID < n) {
			low = mid + 1;
		}
		else {
			high = mid - 1;
			answer = mid;
		}
	}

	cout << answer;
	return 0;
}

mid low high에서 0 0 0이 나오면 다시 처음 과정을 반복하는 게 의문이었다.

+ 추측 1

0 0 0이 되었을 때, else문을 들어가 high = -1이 된다.

unsigned long long 자료형이라 -1이 되는 것이 말이 안 되기 때문에 일어나는 현상 같았다.

 

하지만 1을 넣었을 때도 0 0 0이 되는 경우가 있다. 1을 넣었을 때는 이분 탐색이 정상적으로 종료가 된다.

 

+ 추측 2

high가 -1이 되는 것은 말이 안 되기 때문에 초기 선언 값을 다시 불러오는 건가?

(게시판에 물어봐야겠다..😥😥)

혹시나 답을 아시는 분이 계신다면 여기에 댓글이나 아래 게시판 링크에 가셔서 도와주세요!

https://www.acmicpc.net/board/view/75941

글 읽기 - 문제를 해결하긴 했지만 제 코드에 궁금한 게 있어서요!

 

---

게시판에 댓글이 달렸다! (추가에다가 추가)

-1은 부호가 없는 정수형(unsigned)에서 처리가 되지 않아 unsigned형태에서 가질 수 있는 최대의 자료 값을 갖는다고 한다! 그래서 무한 루프가 되었던 거 같다.

 

그래서 애초에 high가 -1이 될 일이 없게 코드를 수정해주었다.

#include <iostream>
#include <cmath>
#define ll unsigned long long
using namespace std;

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

	ll n;
	cin >> n;

	ll low = 0;
	ll high = sqrt(9223372036854776000) + 1; //2의 63 제곱
	ll answer = 1;


	while (low <= high) {
		ll mid = (low + high) / 2;

		cout << mid << ' ' << low << ' ' << high << '\n';

		ll MID = mid * mid;
		if (MID <= n) {
			low = mid + 1;
			answer = mid;
		}
		else {
			high = mid - 1;
		}
	}

	cout << answer;
	return 0;
}