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

문제 이해

- 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다.

- 그때 합을 구성하는 제곱수들의 개수를 항의 개수라고 한다.

- N의 항의 개수가 최소가 되도록하는 개수를 구하라.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 128MB

 

<입력>

N: 자연수 (1 ~ 100,000, 10^5)

 

<출력>

항의 최소 개수

 

 

---

문제 풀이

이전에 푼 문제가 DP가 불가능한 그리디 문제였어서 DP를 전혀 생각하지 못했다.

접근 방식에 대해 항상 고민하자.

 

 

이 문제는 DP로 풀 수 있는데,

'dp[a] = b를 a를 나타낼 수 있는 항의 최소 개수는 b개이다.' 라고 정의했다.

 

 

예시를 들면 쉽게 이해할 수 있는데

N = 3)

3 = 1^2 + 1^2 + 1^2

dp[3] = 3이 될것이다.

 

그러나

N = 4)

4 = 2^2

dp[4] = 1이 된다.

 

먼저 dp[3] = 3이다.

그러나 dp[4] = dp[3] + 1(1^1의 가짓수)보다 dp[0] + 1(2^2의 가짓수)가 더 최솟값을 가진다.

1^2 + 1^2 + 1^2 +1^2보다

2^2의 항의 개수가 적은 것이다.

 

이런 식으로 

dp[i - 제곱수] + 1과 dp[i]을 비교하며 계속 dp 배열을 최솟값으로 갱신해주는 문제이다!

for(int i = 1; i <= n; i++){
    for(int j = 1; j * j <= i; j++){
        dp[i] = min(dp[i], dp[i-j*j] + 1);
    }
}

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

int dp[101010];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;

    for(int i = 1; i <= n; i++) dp[i] = i;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j * j <= i; j++){
            dp[i] = min(dp[i], dp[i-j*j] + 1);
        }
    }
    
    cout<<dp[n];
    return 0;
}