[JAVA] 백준 1699번 : 제곱수의 합

 

---

 

• 생각

마지막에 들어갈 수 있는 수는 특정 i의 제곱수이므로 항의 개수는 1개가 늘어나게 된다. 이때 n - i^2중에서 가장 최소에다가 1을 더해주면 된다.

 

• 코드

정답 코드 : 점화식을 이용해서 풀었다.

 

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

public class Main {
	static int N;
	static int[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
        Calculate();
		System.out.println(dp[N]);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
	}

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