PS/BOJ2022. 4. 26. 01:23

제곱수의 합

 

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

 

'PS > BOJ' 카테고리의 다른 글

2225  (0) 2022.04.27
2133  (0) 2022.04.26
2579  (0) 2022.04.25
1912  (0) 2022.04.25
11054  (0) 2022.04.25
Posted by easy16