[Java] BOJ 7626 Four Squares

문제 

문제 링크 https://www.acmicpc.net/problem/17626

• 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다.
• 어떤 자연수는 복수의 방법으로 표현된다.
• 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다.
• 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다.
• 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다.
• 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.
• 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.
• 입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.
• 출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

아이디어

• n + 1 크키의 배열을 제곱수의 개수를 저장하기 위해 생성한다.
• 그리고 배열의 1부터 n까지 초기값을 본인의 수로 저장한다. 
• 왜냐하면 제일 큰 경우의 수가 1의 제곱으로 합을 나타내는 것이기 때문이다.
• 그리고 이중 for문을 사용하여 i번째 배열을 i번째 배열의 값과 i - j * j 번째 배열 값에 1을 더한 값과 비교해서 더 작은 값을 저장한다. 
• 제곱수가 기존 숫자보다 크면 안되므로 j의 범위는  j * j 가 i보다 작을 때까지로 제한한다.

겪은 시행착오

• 처음에는 i번째 배열의 숫자가 규칙성이 있을까 싶어서 열심히 찾아봤지만 실패하였고... 문제를 보자마자 떠올렸던 '배열의 이전 값에 + 1을 하여 풀면되지 않을까'란 생각을 활용해서 풀었다 
• 근래에 풀었던 dp문제 중에서 제일 어렵게 풀었던 것 같다 ㅜㅜ

힘든 싸움이였다...

코드

import java.io.*;
import java.util.*;

public class BOJ17626 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력값
        int n = Integer.parseInt(br.readLine());

        // 제곱값의 개수를 저장할 배열
        int arr[] = new int[n + 1];

        // 배열의 i번째 값을 i값으로 저장
        // 최대 필요한 개수는 1의 제곱으로 다 채우는 경우이므로
        for(int i = 1; i <= n; i++){
            arr[i] = i;
        }

        for(int i = 1; i <= n; i++){
            // 제곱수가 기존값보다 크면 안되므로
            // j * j 가 i보다 작거나 같을때까지 반복
            for(int j = 1; j * j <= i; j++){
                // i번째 배열의 값을 i번째 배열의 값과
                // i번째 배열에서 j의 제곱값을 뺀 값에서 1 더한값 중
                // 더 작은 값을 저장
                arr[i] = Math.min(arr[i], arr[i - j * j] + 1);
            }
        }

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