C++로 풀어보는 제곱수의 합 판별 문제

음이 아닌 정수 c가 주어졌을 때, 다음 조건을 만족하는 두 정수 a와 b가 존재하는지 판별하는 문제입니다.

a² + b² = c

예를 들어 입력이 61이라면, 61 = 5² + 6²이 성립하므로 출력은 True(참)가 됩니다.

문제 해결 접근 방법

이 문제는 완전 제곱수(perfect square) 판별 함수를 활용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 먼저 어떤 수가 완전 제곱수인지 확인하는 함수 isPerfect()를 정의합니다.
• 해당 함수는 인자로 받은 값 x에 대해 제곱근을 구한 뒤, 소수 부분이 없는지(즉, 제곱근에서 내림한 값을 뺀 결과가 0인지) 검사하여 참 또는 거짓을 반환합니다.

메인 로직은 다음 순서로 진행됩니다.

1. c가 0이면 두 수 모두 0으로 표현 가능하므로 true를 반환합니다.
2. i를 0부터 c의 제곱근의 올림값 미만까지 반복하면서, b = c − i²를 계산합니다.
3. 이때 b가 완전 제곱수라면 a = i, b = √b로 표현할 수 있으므로 true를 반환합니다.
4. 모든 경우를 확인했는데도 조건을 만족하지 않으면 false를 반환합니다.

C++ 구현 예시

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isPerfect(int x){
        long double sr = sqrt(x);
        return ((sr - floor(sr)) == 0);
    }
    bool judgeSquareSum(int c) {
        if (c == 0)
            return true;
        int b;
        for (int i = 0; i < ceil(sqrt(c)); i++) {
            b = c - i * i;
            if (isPerfect(b))
                return true;
        }
        return false;
    }
};
main(){
    Solution ob;
    cout << (ob.judgeSquareSum(61));
}

입력

61

출력

1

복잡도 분석

이 알고리즘의 시간 복잡도는 O(√c)입니다. i를 최대 √c번 반복하고, 각 반복마다 제곱근 연산이 상수 시간에 처리되기 때문입니다. 공간 복잡도는 추가 배열 없이 몇 개의 변수만 사용하므로 O(1)입니다.

참고로 이 문제는 투 포인터(two pointer) 기법으로도 해결할 수 있습니다. left를 0, right를 √c로 초기화한 후, left² + right²가 c보다 크면 right를 감소시키고 작으면 left를 증가시키는 방식입니다. 두 방법 모두 효율적이며, 상황에 맞게 선택하면 됩니다.