문제
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
제한사항
입출력 예
1
2
3
4
5
6
7
8
9
| Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
|
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
int numSquares(int n) {
int digit = 1;
vector<int> item(n+1, 1);
item[0] = 0;
// 1...n 까지 제곱수 끼리의 합을 만드는 방법은
// item[n] = item[n - sqrt(i)] + 1 이며,
// 가장 수가 적게 만들어야 하므로 i를 1부터 최대 제곱근까지 검사
for(auto i = 1 ; i <= n ; ++i){
// 현재 i까지의 최대 제곱근 검사
int sr = sqrt(i);
if((sr - floor(sr)) == 0){
digit = sr * sr;
}
// 1부터 현재 i까지의 최대 제곱근까지,
// 제곱끼리의 합이 i를 만족하며 갯수가 최소인 갯수를 검사
int minVal = INT_MAX;
for(auto j = 1 ; (j*j) <= digit ; ++j){
int val = item[i] + item[i - (j*j)];
minVal = min(minVal, val);
}
// 찾은 최소값을 현재 item[i] 에 저장
item[i] = minVal;
}
return item[n];
}
};
|
