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

---

0. 문제

 

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

 

1. 아이디어

 

1) 야호!!!

 

2) 해당 문제에서 내가 사용할 dp[i]의 컨셉은 i의 구성하는 최소항들의 개수이다! 그렇다면 그 이후의 수들은 이전 dp값들을 잘 이용한다면 쉽게 최소 제곱수들의 합으로 나타낼 수 있다. ex) dp[80] = dp[64] + dp[16], dp[96] = dp[80] + dp[16]

 

3) (핵심) 예를 들어 32의 경우와 같이 해당 숫자 이하의 가장 큰 제곱수가 반드시 포함되어야만 하는 건 아니다. ex) 32 = 16 + 16 (O), 25 + 4 + 2 + 1 (X) 그래서 가장 가까이에 있는 제곱수부터 1까지의 케이스를 확인하며 최솟값을 찾으면 된다!

 

2. 소스코드

 

#include <iostream>
#include <algorithm>
#include <math.h>
int dp[100001];
int main()
{
    int N, cur = 1; // cur은 현재 값에서 가장 가까운 제곱수
    std::cin >> N;
    for (int i = 1; i <= (int)sqrt(N); i++)
        dp[i * i] = 1; //제곱수들은 항의 최소 개수를 1로 초기화
 
    for (int i = 1; i <= N; i++)
    {
        if (dp[i])
        {
            cur = i;
            continue;
        }
        int result = dp[i - cur] + dp[cur];
        for (int j = sqrt(cur) - 1; j > 0; j--)
            result = std::min(result, dp[i - j * j] + dp[j * j]);
 
        dp[i] = result;
    }
    std::cout << dp[N];
}

 

3. 결과

 

 

4. 피드백

 

• 쉬워보였는데 정말 예상치도 못하게 애먹었다..

• 역시 아직 실력이 많이 부족하다.

• 항상 많은 예외가 존재하니 할 수 있는 최대한의 경우의 수를 고려해야한다!

---