4331: [GESP202409六级] 小杨和整数拆分
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## 题目背景
2024 年 9 月 GESP C++ 六级编程第 1 题
## 题目描述
小杨有一个正整数 $n$，小杨想将它拆分成若干个完全平方数的和，同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为 $n$ 的完全平方数的最少数量。
输入
## 输入格式
第一行包含一个正整数 $n$，含义如题面所示。
输出
## 输出格式
输出一个整数，代表总和为 $n$ 的完全平方数的最少数量。
样例输入 复制
18样例输出 复制
2提示
## 样例1
```input1
18
```
```output1
2
```
## 样例解释
$18=9+9=16+1+1$ ，其中最少需要 $2$ 个完全平方数。
## 数据范围
| 子任务编号 | 数据点占比 | $n $ |
| ---------- | ---------- | ----------- |
| 1 | $20\%$ | $\leq 20$ |
| 2 | $40\%$ | $\leq 1000$ |
| 3 | $40 \%$ | $\leq 10^5$ |
对于全部数据，保证有 $1 \leq n \leq 10^5$ 。