[BOJ] 1699번: 제곱수의 합

1699번: 제곱수의 합

해법

DP, 동전2 문제와 굉장히 유사하다. 분명히 정올 준비를 하면서 이 문제를 풀어 봤음에도 불구하고 처음에는 n보다 작으면서 가장 가까운 제곱수를 빼주는 것으로 생각했는데 그렇게 하니까 32 = 16 + 16같은 반례에 막혔다.(당연하다... ㅠ)

그래서 다시 생각한 것이 제곱수들의 리스트가 주어질 때 i를 범위 내의 제곱수들로 뺀 수의 최소 구성 개수 중에서 가장 작은 것을 고르는 것으로 생각했다.(= min(D[i - sqrt_list[j]]) )

그래서 나온 점화식은 다음과 같다.

int Min = dp[i - sqrt_list[0]];
for (int j = 1; j <= sIdx; ++j) // sIdx는 i범위 내 제곱수의 최고 인덱스를 나타낸다.
    Min = std::min(Min, dp[i - sqrt_list[j]]);
dp[i] = Min + 1;

해법을 찾는 데 결정적인 힌트는 친구가 1, 2, 3 더하기랑 비슷한데? 해서 다시 생각해 보니 i범위 내에 있는 모든 제곱수를 빼보면 되겠구나라는 꺠달음을 얻었다.

int f(int n) {
    if (n == 0) return 0;
    if (n < 0) return 987654321;
    if (dp[n] > 0) return dp[n];
    int idx = find_close(n);
    dp[n] = 1 + std::min({ f(n - sqrt_list[idx]), f(n - sqrt_list[idx - 1]), f(n - sqrt_list[idx - 2])});
    return dp[n];
}

그래서 이렇게 코드를 짰는데 메모리 초과가 뜨길래 전반적인 형태는 유지하면서 범위, for문으로 바꿔줬더니 "맞았습니다"를 받았다.

#include <cstdio>
#include <algorithm>
#include <cmath>

int dp[100001] = { 0, 1, 2, 3 }, n, sqrt_n, sqrt_list[320];

int main()
{
    scanf("%d", &n);
    sqrt_n = (int)ceil(sqrt(n));
    for (int i = 1; i <= sqrt_n + 1; ++i)
        sqrt_list[i - 1] = i * i;

    int sIdx = 0;
    for (int i = 4; i <= n; ++i) {
        if (i == sqrt_list[sIdx + 1]) sIdx++;
        int Min = dp[i - sqrt_list[0]];
        for (int j = 1; j <= sIdx; ++j)
            Min = std::min(Min, dp[i - sqrt_list[j]]);
        dp[i] = Min + 1;
    }
    printf("%d\n", dp[n]);

    return 0;
}