백준 17626번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

import static java.util.Collections.*;

public class Main {
public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int count = 0;
   int N = Integer.parseInt(br.readLine());

   int[] dp =new int[N+1];

   Arrays.fill(dp,Integer.MAX_VALUE);
   dp[0] = 0;

   for (int i = 1 ; i <= N; i++)
   {
       for (int j = 1; j *j<=i;j++)
       {
           if (dp[i] > dp[i-j*j]+1)
           {
               dp[i] = dp[i-j*j]+1;
           }
       }
   }

    System.out.println(dp[N]);



}


}


greedy로 풀려했다가 안 풀려 지피티를 이용하여 dp로 푸는걸 알았다. dp식도 너무 어렵고 그냥 다 어렵다. 이제는 문제 풀기보다는 복습을 해야할 것 같다.