[동적프로그래밍] 백준 1699번 제곱수의 합(C++)

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

 

문제에 대한 설명부터 하겠다.

숌크라테스는뭐여

쨋든

 

자연수 n에 대해서는 제곱수들의 합으로 나타낼 수 있다고 한다.

 

예시의 숫자들과 같이 11은 = 3^2 + 1^2 + 1^2인데

 

뭐 최악의 경우는 1의제곱으로만 이루어져있을수도 있고

쨋든!

 

문제의 흐름이 뭔가...

뭔가....

뭔가!!!!!

 

dp문제 1로 만들기하고 유사한거같은데..나만그래?

https://lee-soo.tistory.com/13

[동적프로그래밍] 백준 1463번 1로 만들기(C++)

어 어..?

 

여기서도 간과할 수 있는게, "가장 큰 제곱수로 나누고 남은값 그 다음 제곱수 or 1로 더하면 되는거 아님?"

이다.

 

예를들어 19에 대해서

 

가장 큰 제곱수가 뭐냐

16이고

그다음은?

1이네,,??
그럼 16 +1+1+1 =4가지야

 

근데 1+9+9로도 될 수 있다 이거야

 

아 그럼 이것도 dp인거같네...

아까와 같이 그러면

기본 값을 dp[i]=dp[i-1]+1로 해도 될것이다 (1의 제곱을 더한거잖아)

그다음에 dp[i]에 대해서 i의 제곱근보다 작은 값들에 대해서 값들 더해주면 되는거 아닌고?

 

for (int j = 1; j < (int)sqrt(i); j++)

            dp[i] = min(dp[i], dp[j * j] + dp[i - j * j]);

 

이렇게

그럼 모든 제곱근의 경우의수를 지나쳤으니까 맞겠지

 

 

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

int dp[1000001];

int main()

{

    int N;

    cin >> N;

    for (int i = 1; i <= 1000; i++)

        dp[i * i] = 1;

    for (int i = 2; i <= N; i++)

    {

        if (dp[i] == 1)

        {

            // cout << "넘어가는 식과 그 값  dp[ " << i << " ] : " << dp[i] << "\n";

            continue;

        }

        int temp_square = (int)sqrt(i);

        // 그 전까지 가장 큰 제곱근을 찾는 식

        dp[i] = dp[temp_square * temp_square] + i - temp_square;

        // cout << temp_square << " " << dp[temp_square * temp_square] << " " << i - temp_square << "\n";

        int temp_n;

        for (int j = 1; j < (int)sqrt(i); j++)

            dp[i] = min(dp[i], dp[j * j] + dp[i - j * j]);

    }

    cout << dp[N] << endl;

}

짜잔~

 

사실 이 문제는 내가 처음으로 알고리즘 답 안보고 빠르게 답을 구했던 문제라 애정이 많이간다

 

사랑해 제곱수의 합 구하기야~~