[JAVA] 백준 1699 - 제곱수의 합

 

 

 

🤔문제 접근

처음에 점화식을 구하지 못하고 

Math.sqrt(N) 을 한 값을 N에서 빼주고 answer+1 해주는 방식으로 

단순 반복문으로 해결하려고 했다. 하지만 이 경우는 항의 최소를 구할 수 없는 방법이었다.

 

어떤 수 N은 N-1보다 작은 제곱수들 중 최소 제곱수들의 합 + 1이라는 규칙을 갖고 있다.

예를 들어 15는 

(15-1) 의 최소 제곱수의 합 +1

(15-4) 의 최소 제곱수의 합 +1

(15-9) 의 최소 제곱수의 합 +1 이다.

문제에선 항이 최소일 때를 구하는 것이므로 이 중 최소 값을 구하면 된다.

 

🚨CODE

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


public class Main {

	public static void main(String[] args) throws Exception  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n+1];
		
		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;
				}
			}
		}
		
		System.out.println(dp[n]);
		
	}
}