(C++) - 백준(BOJ) 2417번 : 정수 제곱근

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

2417번: 정수 제곱근

이분탐색 문제였습니다.

 

 

📕 풀이방법

📔 풀이과정

 mid에 제곱을 한다면 long long범위를 초과할 수 있습니다. overflow발생을 막기 위해 num에 루트를 씌웁니다. sqrt(num)이상이 되는 mid를 찾는 것으로 해결할 수 있습니다. 이 mid는 이분탐색을 시행해 찾습니다.

 

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll num;
ll binarySearch(){
    ll l = 0;
    ll r = sqrt(num);
    while(l <= r){
        ll mid = (l + r) / 2;
        if(mid  < sqrt(num)) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}
int main(){
    cin >> num;
    cout << binarySearch();
}

---

📕 Test Case

 *질문게시판

 input : 1

 답 : 1