백준 17626번 Four Squares (JAVA)

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

17626번: Four Squares

 

저는 DP를 이용하여 문제를 해결하였습니다.

DP를 이용해 이전에 계산한 값을 다시 계산하지 않도록 하였습니다.

숫자가 해당 숫자의 제곱근의 제곱과 같은지를 확인하고 같다면 1을 리턴하고 같지 않다면 제곱근부터 1까지 줄여나가면서 숫자를 줄여나가면서 계산하였습니다.

 

package BOJ.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.function.Function;

public class BOJ_17626 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int[] dp = new int[n+1];
        int result = cal(n,dp);
        System.out.println(result);
    }
    private static final int INF = 987654321;
    private static final int NOT_VALID = 0;
    private static int cal(int n, int[] dp) {
        if(dp[n] != NOT_VALID){
            return dp[n];
        }
        int result = INF;
        for(int i = (int)Math.sqrt(n) ; i >= 1 ; i--){
            if(n == i * i){
                return 1;
            }else{
                result = Math.min(result,cal(n - i*i, dp)+1);
            }
        }
        dp[n] = result;
        return result;
    }

}