# include <bits/stdc++.h> using namespace std ; int coin [114514] , dp [114514] = {0} ; int main ( ) { int a ; cin >> a ; for ( int i = 1 ; i <= a ; i ++ ) { for ( int j = 1 ; j * j <= i ; j ++ ) { if ( dp [i] != 0 ) { dp [i] = min ( dp [i - j * j] + 1 , dp [i] ) ; } else { dp [i] = dp [i - j * j] + 1 ; } } } cout << dp [a] << endl ; return 0 ; }