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

金弘均·2021년 9월 16일
1

Baekjoon Online Judge

목록 보기
168/228
post-thumbnail

# Appreciation

/*
 * Problem :: 3933 / 라그랑주의 네 제곱수 정리
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 30 을 제곱수 3개로 만들 수 있는 방법이 x 가지라면,
 *   31 을 제곱수 4개로 만들 수 있는 방법을 찾는데 도움이 되지 않을까?
 *   + YES <= 31 = (a^2 + b^2 + c^2) + 1^2
 *     DP 로 풀자
 *     # dp[i][j] = j 개의 제곱수의 합으로 i 를 표현할 수 있는 경우의 수
 *
 * Point
 * - 3^2 + 4^2 와 4^2 + 3^2 가 같다
 *   + 중복을 피하기 위해
 *     1^2 를 사용해서 만들 수 있는 경우의 수,
 *     1^2, 2^2 를 사용해서 만들 수 있는 경우의 수,
 *     1^2, 2^2, 3^2 를 사용해서 만들 수 있는 경우의 수,
 *     ...
 *     # 위와 같은 방법으로 차례차례 구해나가자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Process
    int S = (1<<15); /* max(N)=2^15-1 */
    int dp[S][4+1]; /* dp[i][j] = j 개의 제곱수의 합으로 i 를 표현할 수 있는 경우의 수 */
    memset(dp, 0, sizeof(dp));
    for (int i=1; i*i<S; i++) {
        dp[i*i][1] = 1; /* 그 자체로 이미 제곱수인 경우 */
		
        /* 방법 1. */
        /* 현재 1^2, 2^2, ..., (i-1)^2 들의 제곱수를 사용해서
         * j-i*i 를 만들 수 있는 경우의 수는 이미 계산되어있음
         * 이제, i*i 라는 제곱수를 사용해서 j 를 만들 수 있는 경우의 수 계산 */
        for (int j=i*i; j<S; j++) {
            dp[j][2] += dp[j-i*i][1];
            dp[j][3] += dp[j-i*i][2];
            dp[j][4] += dp[j-i*i][3];
        }
		
        /* 방법 2. */
        /* 현재 1^2, 2^2, ..., (i-1)^2 들의 제곱수를 사용해서
         * j 를 만들 수 있는 경우의 수는 이미 계산되어있음
         * 이제, i*i 라는 제곱수를 사용해서 j+i*i 를 만들 수 있는 경우의 수 계산 */
//        for (int j=1; j+i*i<S; j++) {
//            dp[j+i*i][2] += dp[j][1];
//            dp[j+i*i][3] += dp[j][2];
//            dp[j+i*i][4] += dp[j][3];
//        }
    }

    // Set up : Input
    while (true) {
        int N; cin >> N;
        if (N == 0) break;

        // Process
        int ans = 0;  /* 4개 이하의 제곱수의 합으로 N 을 표현할 수 있는 경우의 수 */
        for (int i=1; i<=4; i++) {
            ans += dp[N][i];
        }

        // Control : Output
        cout << ans << endl;
    }
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글