제곱수의 합
dp[i] = Math.min(dp[i], dp[i - j*j] + 1 );
ex)
dp[0]=0
dp[1]=1
...
dp[8] = dp[4] + 1 = 2
dp[4] = dp[0] +1 = 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static Integer[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
dp = new Integer[N + 1];
dp[0]=0;
for ( int i = 1 ; i <= N ; ++i) {
dp[i]= i;
//제곱수에 대한 조건 target이하여야 계산 가능.
//j는 1인 경우는 초기화조건과 중복계산이므로 2부터 시작.
for ( int j=2; j*j <= i ; ++j) {
//실수 : dp[i-1]+1 이전값과의 비교는 의미가 없고, dp[i]와 비교하지 않게되어 최적값이 저장되지 않는다.
//dp[i] = Math.min(dp[i-1]+1, dp[i - j*j] + 1 );
dp[i] = Math.min(dp[i], dp[i - j*j] + 1 );
}
}
System.out.println(dp[N]);
br.close();
}
}
참조:
https://blog.naver.com/occidere/220792326120