백준 1699번 제곱수의 합 - C++ 풀이

---

 

1. dp(n) : n을 제곱수들의 합으로 표현할 때에 그 항의 최소 개수
2. dp(n) = min(1 + dp(n-i*i))

 

1. dp(n) : n을 제곱수들의 합으로 표현할 때에 그 항의 최소 개수

 dp(n)을 위와 같이 정의하자.

 

2. dp(n) = min(1 + dp(n-i*i))

  n을 표현하는 제곱수 중 하나로 i*i를 골랐다고 가정하자. 이제 (n - i*i)를 제곱수들의 합으로 표현해야 하므로, dp(n) = 1 + dp(n-i*i)가 된다. 따라서 i*i가 n 이하인 모든 i에 대해 dp(n) = 1 + dp(n-i*i)값을 계산하고, 그중 최솟값을 찾으면 된다.

 기저 사례는 n이 1 이하일 때, dp(0) = 0, dp(1) = 1.

 

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

typedef long long ll;

int N;
int cache[100001];

// dp(n): n을 제곱수들의 합으로 표현할 때에 그 항의 최소 개수
int dp(int n) {
    if (n <= 1) return n;
    
    int& ret = cache[n];
    if (ret != -1) return ret;
    
    ret = n;
    
    for (ll i=1; i*i<=n; i++) {
        ret = min(ret, 1 + dp(n-i*i));
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));

    cin >> N;
    cout << dp(N);

    return 0;
}