<Algorithm> 212. 제곱수의 합(BOJ)

1. 1699번 제곱수의 합(BOJ)

   사용 알고리즘 :  DP

• 2019/05/31 - [공부/Algorithm] - 211. 동전(BOJ) 이문제와 유형이 비슷하다고 해서 한번 풀어보았다,

• 동전 문제보다는 일반적인 DP 방식으로 접근해서 풀었다. 

문제에 대한 접근&생각

1. 최대 100000의 숫자 중 가장 최소 항 조합 -> 약 1~300까지 조합 -> 너무 많은 경우의수 -> DP!
2. 처음 1^2 부터 시작하는 경우를 배열에 저장 -> ex) 11 = 1^2 + 1^2 ~ 자기 개수만큼
3. 제곱수와 대상숫자가 같은 경우는 하나의 항이 최소가 됨
4. 누적되있는 결과와 현재 조합할 수 있는 결과 중 작은 것이 최소항

코드 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        /***************************
         * DP를 이용하여 이전 항 개수와
         * 현재 가능한 개수 중 최소값으로
         * 선택하여 누적한다. 
         ***************************/
        dp[0] = 1;
        for(int i = 1; i <= n; i++)
            dp[i] = i;
        
        for(int i = 2; i*i <= n; i++) {
            for(int j = i*i; j <= n; j++) {
                if(j-i*i == 0) {
                    dp[j] = dp[0];
                }else {
                    dp[j] = Math.min(dp[j-i*i]+1, dp[j]);
                }
            }
        }
        System.out.println(dp[n]);
    }
}