제곱수의 합

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

// 코드

import java.util.*;
import java.io.*;
 
public class Main{ 
  
  public static void main(String[] args) throws Exception{
    // Please Enter Your Code Here
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in)); 
    
    int   N  = Integer.parseInt(br.readLine());
    int[] dp = new int[N + 1];
    
    for(int i=1; i<=N; ++i) {
      dp[i] = i;
      for(int j=1; j*j<=i; ++j) if(dp[i] > dp[i - (j*j)] + 1) dp[i] = dp[i - (j*j)] + 1;
    }
    
    bw.write(String.valueOf(dp[N])); 
    bw.flush();
    bw.close();
    br.close();
  } 
}