[백준/DP/C++] 1699번 제곱수의합

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

1699번: 제곱수의 합

처음에는 n보다 작은 제곱수 중 가장 큰 제곱수부터 차례로 빼는 방법을 사용했는데 그러면 43같은 반례가 나왔다
ex)
43 = 6² + 2² + 1² + 1² + 1² (5개)
43 = 5² + 3² + 3² (3개)

그래서 dp[n]은제곱수 항의 최소개수로 정하고 n에서 작은 제곱수부터 빼주면서
dp[n] = dp[n - 제곱수] + 1 의 최소값을 구했다

#include <bits/stdc++.h>

using namespace std;
int n;
int dp[100001] ={0};

int main(void) {
    cin >> n;

    for(int i=1; i<=n; i++){
        dp[i] = i;
    }

    for(int i=2; i<=n; i++){
        for(int j=1; j*j<=i; j++){
            dp[i] = min(dp[i], dp[i-j*j]+1);
        }
    }
    cout << dp[n] << endl;

    return 0;
}

참고
https://chanhuiseok.github.io/posts/baek-10/

반응형