BOJ 1699 - 제곱수의 합

링크: https://www.acmicpc.net/problem/1699

문제

주어진 N을 최소 몇 개의 제곱수의 합으로 표현할 수 있는 지 구하는 문제이다.

문제를 풀기 전에, 라그랑주 네 제곱수 정리를 알고 있으면 좋다.

백준 온라인 저지에 문제로도 등장했다.

BOJ 3933 - 라그랑주의 네 제곱수 정리

요약하면, 모든 양의 정수가 많아야 4개의 제곱수의 합이라는 정리인데, 다시 말하면 이 문제의 정답은 최대 4라는 뜻이다.

\(x^a + y^b + z^c + w^d = N\) 에서 \(a,~b,~c,~d\) 를 모두 확인해 볼 필요는 없다. 라그랑주의 정리에 의하면 모든 \(a,~b,~c\)를 찾았는 데 없으면 4개로 표현할 수 있기 때문이다.

즉, 3중첩 반복문으로 해결 가능하다.

코드