코드리뷰 - 라그랑지

a, b, c, d 네 수를 찾아야 하는데, 이 네 수는 중복이 되어도 상관없다. 즉, a = b = c = d = 1일 수도 있다.

또한, 네 수가 모두 존재할 필요도 없다.

이럴 경우에, 가능한 모든 경우의 수를 구하는 것이기 때문에 a = 1, b = c = d = 0의 경우부터 하나씩 찾아낸다.

정석대로면 4중 for문을 사용해 a, b, c, d의 값을 찾아야 하지만 문제에서 말했듯이 시간초과에 걸릴 수 있으므로

a, b, c를 통해 d를 계산해내는 방식을 통해 for문을 하나 줄인다.

하나씩 찾을 때, 네 개의 숫자가 중복되는 경우(1, 1, 3, 5와 3, 1, 5, 1 등)를 피하기 위해 a ≤ b, b ≤ c, c ≤ d라는 조건을 건다.

#include < iostream > 
#include < cmath > 
using namespace std; 
  
int main() 
{ 
    int num, a, b, c, d, count = 0; // 네 개의 상수, 총 갯수
    cin >> num; // 네제곱수를 입력받음
    for (a = 1; a*a <= num; a++) // a 값을 찾음
    { 
        if (a*a == num) count++; // a²이 num일 경우 갯수 추가
        else { 
            for (b = a; b*b <= (num - a*a); b++) // a²이 num이 아닐 경우, b 값을 찾음
            { 
                if (a*a + b*b == num) count++; // a²+ b²이 num일 경우 갯수 추가
                else { 
                    for (c = b; c*c <= (num - a*a - b*b); c++) // a²+ b²이 num이 아닐 경우, c 값을 찾음
                    { 
                        if (a*a + b*b + c*c == num) count++; // a²+ b²+ c²이 num일 경우 갯수 추가
                        else 
                        { 
                            int d = sqrt(num - a*a - b*b - c*c); // a²+ b²+ c²이 num이 아닐 경우, d 값을 찾음
                            if (d >= c && a*a + b*b + c*c + d*d == num) count++; // a²+ b²+ c²+ d²이 num일 경우 갯수 추가
                        } 
                    } 
                } 
            } 
        } 
    } 
    cout << count << endl; // 총 갯수 출력
}

* cmath - C++로 구현된 여러 수학 함수를 담은 헤더파일. C에서의 math.h와 동일.