> For the complete documentation index, see [llms.txt](https://hoilzz-til.gitbook.io/docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hoilzz-til.gitbook.io/docs/old/algorithm/undefined-2/new/2-3/leet-279-perfect-square.md).

# perfect squares

정수 n이 주어졌을 때, 그 n을 제곱 값의 합으로 나타낼 수 있는 식이 있다고 하자.

12 = 2^2 + 2^2 + 2^2 12 = 3^2 + 1 + 1 + 1

등 이 있다. 첫번째는 3개의 숫자로, 두번째는 4개의 숫자로 식을 나타낼 수 있다.

식을 나타낼 수 있는 최소 숫자의 개수를 구하자.

모든 경우의 수를 구해서 최소 값을 구하면 될거 같았다. 바로 떠오른건 DFS로 차례차례 구하는건데 이렇게 될 경우 불필요한 연산이 필요하게 된다. DFS로 풀게 될 경우 연산을 깊게 실행할 필요 없이 최소 n을 구할 수 있다.

```c
class Solution {
public:
    int numSquares(int n) {
        if(n <= 3) {
            return n;
        }
        queue <pair<int, int>> q;
        q.push(make_pair(n, 0));
        int min = n;

        while(!q.empty()) {
            int nextNum = q.front().first;
            int nextCnt = q.front().second;
            q.pop();
            int i = 1;

            while(nextNum >= i*i) {
                i += 1;
            }
            i -= 1;
            nextCnt += 1;

            for(;i>=1; i--) {
                int temp = nextNum - (i * i);
                if(temp == 0) {
                    if(min > nextCnt) {
                        min = nextCnt;
                    }
                }
                if(nextCnt < min) {
                    q.push(make_pair(temp, nextCnt));
                }
            }

        }
        return min;
    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://hoilzz-til.gitbook.io/docs/old/algorithm/undefined-2/new/2-3/leet-279-perfect-square.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.