[백준] 3933번 : 라그랑주의 네 제곱수 정리 (C++)

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

---

 

문제)

양의 정수는 많아야 4개의 제곱수로 표현할 수 있다고 한다. 이 이론을 라그랑주의 네 제곱수 정리라고 한다.

 

이 정리는 조제프루이 라그랑주가 1770년에 증명했다.

우리는 이 이론을 증명하거나 새로운 이론을 발견할 필요는 없고, n이 주어졌을 때 4개 이하의 양의 제곱수의 합으로 n을 만들 수 있는 경우의 수를 구하려고 한다.

 

경우의 수를 구할 때 제곱수의 순서가 바뀌는 경우는 같은 경우로 본다.

 

따라서 3^2 + 4^2 과 4^2 + 3^2는 같은 경우이다.

N이 25일 때 4개 이하의 제곱수의 합으로 표현 할 수 있는 경우는 1^2 + 2^2 + 2^2 + 4^2, 3^2 + 4^2, 5^2 이렇게 3가지이다.

 

 

 

입력 :

입력은 최대 255줄이다. 각 줄에는 2^15보다 작은 양의 정수가 하나씩 주어진다. 마지막 줄에는 0이 하나 있고, 입력 데이터가 아니다.

 

 

 

출력 :

각 테스트 케이스에 대해서 입력으로 주어진 n을 많아야 4개의 제곱수로 나타내는 경우의 수를 출력한다.

 

 

 

 

 

 

풀이)

 

// 3933. 라그랑주의 네 제곱수 정리
#include <iostream>
#include <vector>
 
using namespace std;
 
int t;
int dp[33000][200][5];
 
int recur(int cur, int prev, int cnt)
{
    // 조건을 만족하지 못한다면 0 리턴
    if (cur < 0 || cnt < 0 || prev * prev > t) return 0;
 
    // 조건을 만족하는 경우에만 1 리턴
    if (cur == 0) return 1;
 
    if (dp[cur][prev][cnt] != -1) return dp[cur][prev][cnt];
 
 
    int ret = 0;
 
    // 다음 수로 넘어간다.
    ret = recur(cur, prev + 1, cnt);
 
    // 해당 제곱수로 뺄 수 있으면 뺀다.
    if (cur >= prev * prev) ret += recur(cur - (prev * prev), prev, cnt - 1);
 
 
    dp[cur][prev][cnt] = ret;
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    fill(&dp[0][0][0], &dp[32999][199][4], -1);
    
    while (cin >> t)
    {
        if (t == 0) break;
 
        cout << recur(t, 1, 4) << '\n';
 
    }
 
    return 0;
}
 

 

 

---

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

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