[BOJ] 제곱수의 합(1699)

[백준(BOJ)] 제곱수의 합(1699) C++

문제 : BOJ_1699번 제곱수의 합

문제 설명

DP

DP로 풀 수 있는 기본문제 동전 2와 유사한 제곱수의 합 문제입니다.
1부터 10만까지의 수 중 하나가 주어졌을 때, 그 수를 제곱수로 표현할 수 있는 최소항 개수를 구하는 문제입니다.

예를 들어, 11의 경우엔 11 = 2^2 + 2^2 + 1^2 + 1^2 + 1^2 5개 항도 가능합니다.
하지만, 11 = 3^2 + 1^2 + 1^2 의 3개항으로도 표현이 가능하므로 11이 주어지면 3을 출력해야 합니다.

---

Solution

항의 개수를 최소한으로 쓰기 위해 처음 했던 생각은, 단순하게 주어진 수와 최대한 가까운 제곱수를 구하는 것이었습니다.

예를 들어, 145면 12^2, 100이면 9^2과 같이 가장 가까운 수를 찾은 뒤,

dp[주어진 수] = dp[가까운 수] - dp[주어진 수 - 가까운 수]

로 해결하려 했지만, 무조건 가까운 수만 쓰면 오히려 항의 수가 늘어나는 반례가 있었기 때문에 이 방법은 틀렸습니다.

결국 문제는 제곱수들만 이용해서 dp를 돌려야 하는 게 핵심인데, 이때 주어진 수와 가장 가까운 제곱수만 돌리는 것이 아닌 주어진 수 보다 작은 제곱수라면 계속 최솟값을 확인해 주는 게 방법입니다.

또한, dp 값을 확인해야 하는 수가 제곱수라면 dp[확인해야 하는 수] = 1;로 갱신해 주어야 합니다.

for 문으로 1부터 구해야 하는 값보다 작은 제곱수의 값까지

dp[값] = min(dp[값], (dp[값 - 제곱수의 값] + dp[제곱수의 값]));

으로 해당 값의 최솟값을 계속 갱신해 줍니다.

---

Description

• 최솟값을 갱신하기 전 모두 INF 값으로 dp 값을 초기화해줍니다.
• N이 최대 100,000이므로, 100,001을 INF로 정했습니다.
• sqrt()를 이용해서 해당 값이 제곱수인지를 확인해 주고 제곱수 배열에 넣어주었습니다.

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF 100001
using namespace std;
int main(void) {
    int N;
    cin >> N;
    vector<int> dp(N + 1);
    for (int i = 0; i <= N; i++) dp[i] = INF;
    vector<int> value;
    for (int i = 1; i * i < N; i++) {
        value.push_back(i * i);
    }
    dp[1] = 1;
    int size = value.size();
    for (int i = 2; i <= N; i++) {
        int chk = sqrt(i);
        if (chk * chk == i) {
            dp[i] = 1;
            continue;
        }
        for (int j = 0; j < size; j++) {
            if (value[j] > i) break;
            dp[i] = min(dp[i], dp[i - value[j]] + dp[value[j]]);
        }
    }
    cout << dp[N] << '\n';
    return 0;
}