[알고리즘 문제] 백준1699 - 제곱수의 합

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

1699번: 제곱수의 합

먼저 나의 코드가 틀린 이유는, n을 sqrt(n)로만 뺏다는 점이다. 1 ~ sqrt(n)을 반복하면서 했다면 아마 맞았을 것 같다. 입력으로 12가 들어오는 경우를 보면 한번에 확인할 수 있다.

 

나의 코드 : 12 -> 3^2 + 1^2 + 1^2 + 1^2 + : 4가지 경우

정답 코드 : 12 -> 2^2 + 2^2 + 2^2 : 3가지 경우

 

나의 코드는 12를 sqrt(12)로 먼저 뺏다. 제곱근 하여 12보다 작거나 같은 숫자는 1,2,3이 있는데 여기서 나는 1,2인 경우를 무시하고 3인 경우만 계산을 하였다. 사실 결과를 보면 2^2를 3번 더한 것이 길이는 더 짧다.

 

대충 어떻게 푸는지는 알았는데, 좀 디테일한 부분에서 놓친 것 같다. 아쉬움이 남는 문제다.

---

먼저 문제를 풀기전에 알아야 할 점은,

1. dp[i] = n : i를 표현할 수 있는 제곱수 항의 최소개수는 n을 의미한다.

2. 4,8은 2의 제곱수 이기 때문에dp[4]=1, dp[8]=1이다. 물론 3,9,27..도 마찬가지이다.

 

먼저 dp[i] = i는, i를 구성하는 숫자를 모두 1로 넣는 최악의 경우이다. 뭐 어쨋든 dp[i]=i가 들어가는 경우는 없을 것이다.

 

안쪽 for문에 sqrt(i)까지 반복하는 이유는 위의 2번이 설명할 수 있다. n이 10인 경우 sqrt(10)은 3을 가지는데, 이때 dp[1], dp[4], dp[9]의 경우가 dp[]=1로 최소값을 가지기 때문이다. for문을 돌리는 이유는 1,4,9중에 "최소"가 뭔지 모르기 때문이다(이 부분 때문에 틀렸다)

 

dp[i] = min(dp[i], dp[i - j * j] + 1);에서 중요한 부분은  dp[i - j * j] + 1인데 이 부분을 설명하자면,

"j를 사용한 경우 + j를 사용했기 때문에 +1"이다. 무슨 말인지 잘 모르겠다...

 

i가 15라면 j는 1~3을 가질 것이다.

j : 1 -> dp[15-1] + 1    

j : 2 - > dp[15-4] + 1

j : 3 -> dp[15-9] + 1

 

dp[j*j]인 경우는 무조건 1이다. 2^2, 3^2, 4^2가 무조건 1이기 때문에. 여기서 dp[i-j*j]는 j*j인 경우를 포함시켰다는 의미이다. 즉 사용했기 때문에 사용했다는 의미로 뒤에 +1을 해준다(dp[j*j]=1이기 때문에). 그리고 사용했기 때문에 i에서 j*j을 빼줘야 한다.

 

그러면 다시 dp[i-j*j]인 경우를 살펴볼 것이다. 이것도 역시 위의 과정을 반복하는데, 이 값은 이미 dp[]에 저장되어 있다. 이 과정을 반복하면서 최소인 경우를 dp[i]에 넣으면 된다.

#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;

int main()
{

    int n;
    cin >> n;

    int dp[100001] = {0};

    for (int i = 1; i <= n; i++)
    {
        dp[i] = i; // 먼저 가장 최악의 경우인 1^2로 구성되는 방법
        for (int j = 1; j <= sqrt(i); j++)
        {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }

    cout << dp[n];
    return 0;
}