백준 2417[정수 제곱근]

1. 문제설명

문제 URL : https://www.acmicpc.net/problem/2417

이 문제는 주어진 자연수  n 에 대해, 그 수보다 크거나 같은 가장 작은 제곱수를 찾는 문제입니다. 예를 들어,  n 이 10일 경우, 4의 제곱인 16이 10보다 크거나 같은 최소의 제곱수입니다. 따라서, 출력값은 4가 됩니다.

2. 정답코드

import sys
input = sys.stdin.readline

# 입력값 n을 정수로 읽어들임
n = int(input())

# 이분 탐색을 위한 시작점과 끝점 설정
s = 0 
e = 2**63
ans = -1

# 이분 탐색 수행
while s <= e:
    mid = (s + e) // 2  # 중간값 계산
    if mid**2 >= n:     # 중간값의 제곱이 n보다 크거나 같은 경우
        ans = mid       # 가능한 답으로 설정
        e = mid - 1     # 더 작은 범위에서 탐색 계속
    else:
        s = mid + 1     # 중간값의 제곱이 n보다 작은 경우 더 큰 범위에서 탐색

# 정답 출력
print(ans)

 

3. 코드설명

1) 변수 초기화 : 먼저, 입력받은 자연수  n 을 정수로 변환하여 저장합니다. 이와 함께 이분 탐색을 위한 시작점  s 와 끝점  e 를 초기화합니다.  e 는  2^{63} 으로 설정하여 매우 큰 범위까지 탐색할 수 있도록 합니다. 또한, 답을 저장할 변수  ans 를 -1로 초기화합니다.
2) 이분 탐색 수행 : 이분 탐색을 통해  n 보다 크거나 같은 최소의 제곱수를 찾습니다. 먼저 중간값  mid 를 계산한 후,  mid 의 제곱이  n 보다 크거나 같은지 확인합니다. 만약 크거나 같다면, 이 값을 가능한 답으로 설정하고, 더 작은 범위를 탐색합니다. 그렇지 않다면, 더 큰 범위를 탐색합니다.
3) 정답 출력 : 최종적으로 탐색을 마친 후, 찾은 값을 출력합니다.

4. Github으로 확인

coTest/BOJ_EASY/E_BOJ_03_2417.py at main · pcy4196/coTest