문제접근
놓쳤던 부분
•
시간초과
코드
2288 KB
32 ms
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void) {
int n;
int dp[100001];
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
dp[i] = i;
for (int j = 1; j * j <= n; j++)
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
cout << dp[n];
return (0);
}
C++
복사