Intuition

제곱수들만의 합으로 특정 숫자를 구성한다. 이때, 최소한의 숫자가 몇개인지 구하는 문제이다.
LIS의 변형 느낌이다.
이번 문제는 쉽기때문에 간단하게 요약 작성하였다

Approach and Solution

1을 만들기 위해서는 1만 있으면 된다.
2는 1+1, 0+2 모두 가능하지만, 문제 조건상 전자만 가능하다.
3은 1+1+1
4는 1+1+1+1과 0+4 가 가능하다. 따라서 최소 숫자는 후자인 1개가 된다.

즉, $ans[i]=ans[i-j^2]+1$ if $(ans[i]+1>ans[i-j^2]+1)$ 으로 정리할 수 있다.

int numSquares(int n) {
    int ans[10001];
    ans[0]=0;

    for (int i=1;i<=n;i++){
        ans[i]=ans[i-1]+1;
        for (int j=2;i-j*j>=0;j++) { // j<=10000 빼도 될 것 같음
            if (ans[i]>ans[i-j*j]+1) ans[i]=ans[i-j*j]+1;
        }
    }

    return ans[n];
}