[백준-17626] Four Squares - Java

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

17626번: Four Squares

백준 17626번 Four Squares 자바 풀이

난이도: 실버3

 

 

 

코드

import java.util.*;

public class back17626 {

    public static void main(String args[]){

        Scanner scanner = new Scanner(System.in);

        int n=scanner.nextInt();

        int []dp=new int[50001];

        dp[0]=0;

        dp[1]=1;

        for(int i=2;i<=n;i++){

            int min=Integer.MAX_VALUE;

            for(int j=1;j*j<=i;j++){

                min=Math.min(min,dp[i-j*j]);

            }

            dp[i]=min+1;

        }

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

    }

}