[Algorithm]Baekjoon 1699 : 제곱수의 합

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

1699번: 제곱수의 합

int n;
int dp[100001] = { 0 };
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    memset(dp, 0x3f, sizeof(dp));
 
    dp[0] = 0;
    dp[1] = 1;
 
    for (long long i = 2; i <= n; ++i)
    {
        if (i*i <= 100000) dp[i * i] = 1;
        
        for (int j = 1; j * j <= i; ++j)
        {
            dp[i] = min(dp[i], dp[i - j*j] + dp[j*j]);
        }
    }
 
    cout << dp[n];
}
 

 

DP문제는 참 설명하기가 쉽지않은것같다.

10 이라는 숫자를 기준으로 말해보겠다.

여기서 1부터 10까지 (자기자신까지) 돌면서, 10을 구성하는 숫자중에 제곱수가 있다면 10-제곱수 + 제곱수(1)을 dp에 업데이트한다.

제곱수가있다면 하나의 항으로 퉁쳐버릴 수 있기 때문에 반드시 제곱수를 찾아야 한다.

그래서 24번쨰라인의 dp[j*j]는 사실 그냥 1이다. 저거 1로바꿔도 통과된다. 어차피 제곱수라 항이 1개라서 그렇다.

 

그리고 주의해야할 점은 위의 코드처럼 dp테이블 업데이트와 동시에 dp[제곱수] = 1 하는 작업을 하려하면 i를 반드시 int보다 큰 자료형으로 해줘야 한다. if문에서 i*i를 검사할 때, n이 최대 10만이라 10만 * 10만 값을 int크기의 메모리에 담으려는 시도를 하기 때문이다. 10만 * 10만은 100억이라 당연히 int로 못담는다.