C++에서 주어진 숫자보다 큰 다음 완전제곱수 구하는 방법

프로그래밍 문제에서 숫자 n이 주어지면, n보다 큰 다음 완전제곱수를 찾아야 하는 경우가 자주 있습니다. 예를 들어 n = 1000이라면, 그다음으로 가장 가까운 완전제곱수는 1024(=32²)입니다.

이 문제를 해결하는 방법은 매우 간단합니다. 먼저 주어진 숫자 n의 제곱근을 구한 뒤, 해당 값에 대해 내림(floor) 연산을 적용합니다. 그다음 (내림값 + 1)의 제곱을 계산하면 원하는 결과를 얻을 수 있습니다.

알고리즘 단계

n의 제곱근을 구합니다.
제곱근 값에 대해 소수점 이하를 버립니다(내림).
(내림값 + 1)을 두 번 곱하여 제곱한 뒤 반환합니다.

예제 코드

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

int justGreaterPerfectSq(int n) {
    int sq_root = sqrt(n);
    return (sq_root + 1) * (sq_root + 1);
}

int main() {
    int n = 1000;
    cout << "Nearest perfect square: " << justGreaterPerfectSq(n);
}

실행 결과

Nearest perfect square: 1024

위 코드에서 n = 1000일 때 sqrt(1000)은 약 31.62이므로, 내림하면 31이 됩니다. 여기에 1을 더한 32의 제곱인 1024가 최종 결과로 출력됩니다. 이 방법은 O(1)의 시간 복잡도로 동작하기 때문에 매우 효율적입니다.