[2417번] 정수 제곱근

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 탐색을 이용한 풀이

2. 수학적 풀이

두가지 풀이가 존재한다.

1. 이분 탐색을 이용하여 정해를 찾는 방법이 있다.

당연히 start와 end를 지정하고 mid를 찾아가며 답을 찾아내면 된다.

2. 수학적 풀이가 존재한다.

sqrt를 이용하여 root값을 구하고 그것의 제곱이 답과 같다면 정답이 되는 것이고 

root값의 제곱이 답보다 작다면 +1한 값이 정답이 될 것이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <iostream> #include <cstdio> #include <cmath>   using namespace std;   typedef long long ll;   int main() {     ll n;     cin >> n;       ll start = 0;     ll end = sqrt(n);      ll mid;       while (start <= end)     {         mid = (start + end) / 2;         if (mid >= sqrt(n))             end = mid - 1;                  else             start = mid + 1;     }       if (mid * mid == n)         cout << mid;     else         cout << mid + 1;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

#include <iostream>
#include <cstdio>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
    ll n;
    cin >> n;
 
    ll ans = (ll)sqrt(n);
    if (ans*ans == n)
        cout << ans;
    else
        cout << ans + 1;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>