백준 JAVA 17626번 Four Squares

문제 링크: https://www.acmicpc.net/problem/17626

17626번: Four Squares

그리디 알고리즘으로 가장 큰 제곱수를 빼고 나머지에서 가장 큰 수로 계속해서 나가는 형식으로 문제를 접근했지만, 당연히 틀렸다. DP로 풀어야 하는 문제였다.  밑에와 같이 개수=1일 때 가장 작고 그 후에 증가하고 줄어드는 추세를 볼 수 있다.  

dp[1] = 1^2 = 1개

dp[2] = 1^2 + 1^2 = 2개

dp[3] = 1^2 + 1^2 + 1^2 = 3개

dp[4] = 2^2 = 1개

dp[5] = 2^2 + 1^2 = 2개

dp[6] = 2^2 +1^2 + 1^2 = 3개

dp[7] = 2^2 +1^2 + 1^2 + 1^2 = 4개

dp[8] = 2^2 +2^2 = 2개

dp[9] = 3^2 = 1개

~~

dp[25] = 5^2 =1개

dp[26] = 5^2 + 1^2 = 1개

 

이와 같이 계속 나열했으 때 다음과 같은 점화식을 도출할 수 있었다.

dp[i] = min(dp[i-j*j])+1

코드로 작성한다면 다음과 같다. 

import java.util.*;
import java.io.*;


public class Main {

    static int [] dp;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp =new int[n+1];
        dp[0]=0;
        dp[1]=1;
        System.out.println(solve(n));
    }

    public static int solve(int num){

        for(int i=2;i<=num; 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;
        }

        return dp[num];
    }
}