2417번 정수 제곱근

백준 온라인 저지 2417번 정수 제곱근

---

문제 출처 : https://www.acmicpc.net/problem/2417

 

2417번: 정수 제곱근

 

 

 

 

 

풀이 과정

 

 단순하게 0부터 n의 제곱근까지 계산하는 완전탐색을 사용하면 n의 값이 너무 크기 때문에 시간초과가 나게 됩니다.

따라서 연속되는 값들 사이에서 값을 찾을 때 사용되는 이진탐색을 통해 값을 찾았습니다. 

 

 이진탐색으로 값을 찾고나서 그 값의 제곱이 입력값과 같으면 그대로 출력하면 되고, 작다면 +1을 해줘서 출력해주면 됩니다. 

 

 

 

 

 

소스 코드 

#include <iostream>
#include <cmath>
using namespace std;

int main() {

    long long a;
    cin >> a;
    long long s = 0;
    long long e = sqrt(a);
    long long mid;
    
    while(s <= e) {
        mid = (s+e) / 2;
        if(mid >= sqrt(a)) e = mid - 1;

        else s = mid+1;

    }

        if(mid *mid == a) cout << mid << endl;
        else 
            cout << mid+1 << endl;    
}