Backjoon(백준) 1699- 제곱수의 합 (Java)

문제링크

( https://www.acmicpc.net/problem/1699 )

분류 

 - 동적계획법

1. 풀이 힌트

 - 주어진 수 n에서 뺄 수 있는 가장 큰 제곱수를 뺀 결과값의 제곱수들의 합은 이미 구했던 어떤 수의 제곱수들의 합을 나타낸다.

ex) n으로 11이 주어졌을 때 11에서 뺄 수 있는 가장 큰 제곱수는 9이고 11 - 9 = 2이다. 2의 제곱수들의 합은 1^ + 1^이며, 결과적으로 11의 제곱수들의 합은 [ 2의 제곱수들의 합 (1^, 1^) + 3^ ] 이다. 즉, 이미 구했던 2의 제곱수들의 합과 뺄 수 있는 가장 큰 제곱수(+1)를 더한 값이 11을 이루는 제곱수들의 합의 개수가 된다.

2. 풀이 과정

 1) n을 13까지 해서 제곱수의 합들을 공책에 나열하여 규칙을 추론해본다.

 2) 제곱수들의 합의 크기가 이전 값에 비해 1씩 증가하다가 4, 9 등 제곱들이 변할 때 값이 결과 값이 작아지는 것을 알 수 있다.

 3) 12와 같이 다른 제곱수가 2번 들어가는 수도 고려하여 점화식을 도출해야 한다.

 4) 최종 점화식은 dp[i] = dp[i - j * j] + 1이 된다.

  * i는 현재 제곱수의 합을 구하려는 값, j * j 는 i 값에서 뺄 수 있는 제곱수, +1은 j * j을 뺀 횟수를 더해주기 위함.

3. 코드 풀이 (Java)

import java.util.Scanner;

public class SumOfSquares {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[100001]; // 제곱수의 합 갯수 저장.
        
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                if (dp[i] > dp[i - j * j] + 1 || dp[i] == 0) {
                    dp[i] = dp[i - j * j] + 1;
                }
            }
        }
        System.out.println(dp[n]);
        
        
        
        
    }
}