[S2] 1699. 제곱수의 합

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

1699번: 제곱수의 합

보면 간단한 dp문제이다. 하지만, 보다 더 효율적으로 알 수 있는 방법이 존재한다. 

S3에서 해결하였던 four squares 문제와 비슷하다.

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

17626번: Four Squares

우선 dp로 해결해보자. 

그냥 하나하나 찾는 것이다. 입력된 값 n으로 시작하여 1 ~ i^2이 n이 되기 전까지 하나하나 살펴보고, 가장 작은 값을 넣어주는 것이다.

i가 1일때 dp[n - 1] + 1

i가 2일때 dp[n - 4] + 1

...

이렇게 말이다. 이 중에서 가장 작은 값을 넣어주면 된다 코드도 간단하게 다음과 같이 나온다.

#include <cstdio>
#include <cmath>

int main(void) {
    int N, dp[100001]{ 0, 1 }; scanf("%d", &N);

    for (int i = 2; i <= N; i++) {
        dp[i] = 1e9;
        for (int j = std::sqrt(i); j > 0; j--) {
            if(dp[i] > dp[i - j * j] + 1) dp[i] = dp[i - j * j] + 1;
        }
    }
    printf("%d", dp[N]);
}

 

하지만, 이 문제는 하나 엄청난 비밀이 숨겨져 있다. 바로 모든 숫자는 제곱으로 이루어진 숫자로 최대 4개밖에 없다. 제곱수 5개 이상으로 이루어진 숫자가 없다는 것이다. 이유는 나도 잘..

이것을 이용해서 하나하나 살펴보는 방법이 존재한다.

코드는 다음과 같다.

#include <cstdio>

int main(void) {
    int n; scanf("%d", &n);

    int i, j, k, l;
    for (i = 0; i < 318; i++) {
        for (j = i; j < 318; j++) {
            for (k = j; k < 318; k++) {
                int sum = i * i + j * j + k * k;
                if (sum > n) break;
                else if (sum == n) {
                    if (j == 0) printf("1");
                    else if (i == 0) printf("2");
                    else printf("3");
                    return 0;
                }
            }
        }
    }
    printf("4");
}