이번 문제는 공식을 찾아내서 푸는 문제였다.

• cnt배열에 각각 인덱스 값을 값으로 넣는다.
• for문을 sqrt(인덱스값)까지 반복하며 cnt배열에 최소값을 찾아 넣는다.

Code

#include <iostream>
#include <math.h>
#include <algorithm>
#define MAX 100001
using namespace std;

int n;
int cnt[MAX]={0};

void Input(){
    cin>>n;
}

int Solution(int num){
    for(int i=1; i<=n; i++){
        cnt[i]=i;
        for(int j=1; j<=sqrt(i); j++){
            cnt[i]=min(cnt[i], cnt[i-j*j]+1);
        }
    }
    return cnt[num];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    cout<<Solution(n)<<endl;
    return 0;
}