알고리즘

백준 17626번 Four Squares (JAVA)

박카스마시며코딩 2022. 9. 3. 19:05

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

 

17626번: Four Squares

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1

www.acmicpc.net

 

저는 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;
    }

}