[백준(Baekjoon)][자바(java)] 1699 : 제곱수의 합 / 동적계획법

 

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

문제 풀이

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		int dp[] = new int[n+1], i, j;
		for( i = 1; i <= n; i++ )  
			dp[i] = i;	// 1의 제곱으로만 이루어진 항의 개수 == 그 수   
		for( i = 2; i <= n; i++ )
			for( j = 2; j*j <= i; j++ )
				dp[i] = Math.min( dp[i], dp[i-j*j] + 1 );   

		System.out.println( dp[n] );
		
	}

}

 

*  DP

-  dp[i] => 제곱수의 합이 i인 최소 항의 개수
-  최솟값을 구해야하므로, 초기값은 최댓값으로 설정
   자연수 n을 제곱수들의 합으로 표현할 때 그 항의 최대 개수는 n개 이다
 ( ex) 5 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 )
 ( n이 1~3일 경우, 최소 개수 또한 n개이다 )
-  dp[]를 순회하며( 4 <= i <= n ) 2부터 제곱수를 구해( 4 <= j*j <= i )
   dp[i-j*j] ( i에서 j*j를 뺀 수의 최소 항 개수 ) 에 1을 더한 값과 와 dp[i] 를 비교하여 더 작은 값으로 갱신