[백준/BOJ C++] 3933번 : 라그랑주의 네 제곱수 정리 (브루트포스, Gold V)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3933번 : '라그랑주의 네 제곱수 정리' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold V에 해당하며, 문제를 풀이하기 위해 브루트포스(완전탐색) 알고리즘에 대한 이해가 있으면 좋습니다.

 

(사실 이 문제는 지금 Diamond IV 티어를 배정받은 정수론 문제를 풀고 있는데 그 문제를 푸는 데 도움이 될까 해서 같이 풀어보고 있는 문제입니다.)

 

 

3933번 : 라그랑주의 네 제곱수 정리

3933번: 라그랑주의 네 제곱수 정리

 

왜 골드 난이도의 문제인지는 모르겠으나, 다수결의 투표로 Gold V 티어로 배정된 브루트포스 문제입니다.

사실 문제를 풀이하기 전에 브루트포스로 될지는 모르겠다고 생각했는데, 문제 분류를 보고 바로 코드 작성을 시작했습니다.

양의 정수는 많아 봐야 4개의 제곱수로 표현이 가능하다고 하였으므로, 총 4중 for문을 돌려서 성립하는 해의 순서쌍의 수를 count 해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        int cnt = 0, sqrtN = sqrt(N);
        for(int i=1; i<=sqrtN; i++) {
            if(i*i == N) { cnt++; continue; }
            for(int j=i; j<=sqrtN; j++) {
                if(i*i + j*j == N) { cnt++; break; }
                for(int k=j; k<=sqrtN; k++) {
                    if(i*i + j*j + k*k == N) { cnt++; break; }
                    for(int l=k; l<=sqrtN; l++) {
                        if(i*i + j*j + k*k + l*l == N) { cnt++; break; }
                        if(i*i + j*j + k*k + l*l > N) break;
                    }
                }
            }
        }

        cout << cnt << "\n";
    }
}

 

sqrt를 매 반복문마다 수행하면 시간이 많이 걸릴 수 있으므로, sqrtN을 미리 계산해둔 뒤 반복문에서는 상수처럼 사용하는 것이 핵심입니다.

그리고 다음 변수에 대한 계산을 수행하기 전에 미리 지금까지 사용한 정수의 개수로 합을 구성할 수 있는지 확인 후 넘어갑니다.

 

 

 

풀이 코드를 제출하면 위와 같이 1초가 넘어가는 시간에 정답 처리를 받을 수 있습니다.

문제에서 주어진 제한 시간은 2초이기 때문에 넉넉하게 정답 처리를 받을 수 있습니다.