BJ1699 제곱수의 합

https://www.acmicpc.net/problem/1699
사용한 알고리즘 : DP
난이도 : 실버 3

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

문제 접근 방법

DP 알고리즘으로 문제를 해결하기 위해서는 다음의 2 조건을 만족해야한다.
1. 큰 문제를 같은 구조의 작은 문제로 분해할 수 있다.
2. 작은 문제의 최적의 해를 이용해서 큰 문제의 최적의 해를 구할 수 있다.

위의 두 경우를 만족하면 문제를 점화식의 형태로 만들어 풀 수 있다.

점화식

• 자연수 N의 제곱수의 합을 구하는 경우
  - 0보다 크고 N보다 작은 제곱수 j에 대해서
  - j와 자연수(N - j)의 제곱수의 합중에서 가장 수가 적을때가 N의 제곱수이다.

코드

package Java.Y22.M03.D06;

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

public class BJ1699_SumOfSquare {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		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; i - (j * j) >= 0; j++) {
				if(dp[i] > dp[i - (j * j)] + 1) dp[i] = dp[i - j * j] + 1;
				
			}
		}
		System.out.println(dp[N]);
	}

}