챕터3-18. DP | 문제 풀이4 - (1) 백준 No.1699 : 제곱수의 합

제곱수의 합 문제

- 백준 No.9095 : 1, 2, 3 더하기 문제와 비슷함
- https://www.acmicpc.net/problem/1699

문제요약

어떤 자연수 N이 주어지면 이를 N보다 작은 제곱수의 합으로 나타내는 데,
이때의 항의 최소개수를 구해라.

해결 방법

1. D[i] 정의
D[N] = "자연수 N을 제곱수의 합으로 나타내는데 이때의 항의 최소개수"

 

2. 점화식 세우기
정수 N이 주어지면 앞에 어떤 조합들이 오고 맨 뒤에 i^2이 온다고 해보자.

O + O + O + ... + i^2 = N 이 된다.

 

여기서 i^2를 제외시킨 앞의 나머지 항들에 대해서만 생각해보면 D[N] = min(D[N - i^2] + 1) 가 된다.

i^2 이 1^2, 2^2, 3^2, ,.....이 될 수 있기 때문에. i의 범위를 생각해야하는데 이는 문제의 조건에 의해서 i^2 <= N 이 된다.

<Bottom-up 방식>

(1)시간복잡도
= for 문의 반복 횟수 

i의 범위를 계산해 보면은 문제의 조건에 의해서 i^2 <= N 이 된다. 이는 다시 i <= 루트N이 되며
N개의 D를 구해야하고 i의 범위는 루트n이므로 이 문제의 시간복잡도는 O(N루트N) 이 된다.
이를 코드상에서 구현하게 되면 바깥 for문은 N번의 반복, 안쪽 for문은 루트N의 반복이 있게 됨.
(루트N의 반복은 제곱시켜서 아래와 같이 나타낼 수 있음)

 

(2) 구현
-> 'for문을 이용한 반복문'으로 구현

#include<iostream>

using namespace std;

int d[100001];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++){
        d[i] = i; // 최대값을 초기값으로 넣어줌. 1을 i번 하면 최대값이기 때문. 
        for(int j = 1; j*j <= i; j++){
            if(d[i] > d[i -(j*j)] + 1)
                d[i] = d[i -(j*j)] + 1;
        }
    }

    cout << d[n] << "\n";
}