백준-1699번/제곱수의 합 (java)

 

정수 n의 제곱수의 합 최소갯수를 확인하기 위해 크기가 n+1인 dp[n+1]배열을 만들어 준다.

 

정수 a의 최소 제곱수의 합을 구하는 방법

dp[a-1]+1

dp[a-4]+1

dp[a-9]+1

.

.

.

dp[a-(a보다 작은 제곱수 중에서 가장 큰값)]+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;

}

}

}

 

 

 

정답 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		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]);
	}
}