[백준 2417] 정수 제곱근 - Java

📌 문제 링크

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

 

📄 문제 설명

 

 

🧠 문제 접근

N의 범위는 최대 2^63 - 1로, long 타입 범위까지 허용됩니다.

즉, 단순히 0부터 1씩 올리면서 제곱값을 비교하면 시간 초과가 발생합니다.

 

그래서 이 문제는 이진 탐색 (Binary Search) 으로 접근해야 합니다.

 

 

• left = 0, right = n 으로 범위를 잡고,
• mid를 기준으로 이진 탐색 진행
• mid <= n / mid → mid는 제곱해도 n 이하인 수
  • 만족하면 answer = mid, 더 큰 제곱근 가능성 탐색 (left = mid + 1)
  • 아니면 줄이기 (right = mid - 1)

 

✅ 내가 제출한 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());

        long left = 0;
        long right = n;
        long answer = 0;

        while (left <= right) {
            long mid = (left + right) / 2;

            if (mid <= n / mid) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(answer);
    }
}