[백준] 1699. 제곱수의 합

문제

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






풀이

1 = 1 * 1
2 = (1 * 1) + (1 * 1)
3 = (1 * 1) + (1 * 1) + (1 * 1)
4 = (1 * 1) + (1 * 1) + (1 * 1) + (1 * 1) or 2 * 2
...

이런 식이다. 즉 어떤 수 N 은 1 * 1  N 개로 표현할 수 있으며, 이것이 최대 개수가 될 것이다. 하지만 우리는 최소 개수를 구하고 싶다. 최소가 되려면 어떻게 되야할까?

가령 4의 경우 1 * 1 4개로 표현할 수 있지만 2 * 2로 표현하게 될 경우 2의 제곱 1개만으로도 표현할 수 있다. 즉, 제곱수의 경우 1개만으로 표현이 가능하다는 것이다. 따라서 다시 예를 들어보자면 37의 경우 36 + 1이므로 (6 * 6) + (1 * 1) 즉 2개만으로 표현이 가능하다는 것이다.
위에서 예시로 든 37의 경우 d[37] = d[36] + d[1] = 1 + 1 = 2가 최소 개수가 되는 것이다.
또 8의 경우 d[8] = d[4] + d[4] = 1 + 1가 최소 개수가 된다.
결국 d[N] = d[N보다 작은 가장 최대가 되는 제곱수 i] + d[N - i] = 1 + d[N - i] 가 되는 것이다. 써보니까 무슨 수학 공식처럼 됐지만 외우는 것이 아니다.

#include <stdio.h>
#include <iostream>

using namespace std;

int main(){
    int arr[100001] = { 0, };
    for(int i = 1; i < 100001; i++){
        arr[i] = i;
    }

    int N; cin >> N;
    for(int i = 2; i <= N; i++){

        for(int j = 2; j * j <= i; j++){
            arr[i] = min(arr[i], arr[i - j * j] + 1);
        }
    }
    cout << arr[N];
}