백준 3933 라그랑주의 네 제곱수 정리

https://www.acmicpc.net/problem/3933

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 양의 정수는 많아야 4개의 제곱수로 표현 할 수 있다는 라그랑주의 네 제곱수 정리에 따라 어떤 수를 입력 받았을 때 그 숫자가 몇 개의 4개 이하의 제곱수의 합으로 표현 될 수 있는지 구하는 문제입니다. 입력은 2^15보다 작은 숫자가 들어오므로 저는 그냥 for문을 4번 돌려서 해결을 하였습니다.

더하는 과정에서 값이 커질 경우 break를 해주면서 불필요한 횟수를 줄이면 입력이 그렇게 크지 않아서 시간안에 해결이 됩니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <cmath>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int input = 255;
	int num;
	int n = 0;
	
	while(input) {
		n = 0;
		cin >> num;
		if(num == 0)
			break;
		
		int len = (int)sqrt(num);
		
		for(int i = 1; i <= len; i++) {
			if(i*i == num) {
				n++;
				continue;
			}
			for(int j = i; j <= len; j++) {
				if(i*i + j*j == num) {
					n++;
					break;
				}
				else if(i*i + j*j > num)
					break;
				
				for(int k = j; k <= len; k++) {
					if(i*i + j*j + k*k == num) {
						n++;
						break;
					}
					else if(i*i + j*j + k*k > num)
						break;
					
					for(int l = k; l <= len; l++) {
						if(i*i + j*j + k*k + l*l == num) {
							n++;
							break;
						}
						else if(i*i + j*j + k*k + l*l > num)
							break;
					}
				}
			}
		}
		
		cout<<n<<'\n';
		input--;
	}
	
	return 0;
}