[알고리즘] four squares

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.text.MessageFormat;
import java.util.Arrays;
import java.util.Objects;

/**
 * packageName    : org.example.fourSquares
 * fileName       : Main
 * author         : ipeac
 * date           : 2023-09-06
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2023-09-06        ipeac       최초 생성
 */
public class Main {
    public static void main(String[] args) {
        try (
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ) {
            String input = br.readLine();
            Number naturalNumber = Number.from(input);
            int[] dp = new int[naturalNumber.getValue() + 1];
            
            int answer = 1;
            // 제곱수는 최대 5이기에  5 설정
            Arrays.fill(dp, 5);
            dp[0] = 0;
            for (int i = 1; i <= naturalNumber.getValue(); i++) {
                for (int j = 1; j * j <= i; j++) {
                    int square = j * j;
                    dp[i] = Math.min(dp[i], dp[i - square] + 1);
                }
            }
            
            System.out.println(dp[naturalNumber.getValue()]);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static class Number {
        private final int value;
        
        public Number(int value) {
            if (!(1 <= value && value <= 50_000)) {
                String errorMessage = MessageFormat.format("1 이상 50,000 이하의 정수를 입력해주세요. (입력값: {0})", value);
                throw new IllegalArgumentException(errorMessage);
            }
            this.value = value;
        }
        
        public static Number from(String value) {
            Objects.requireNonNull(value);
            int parsedValue = Integer.parseInt(value);
            return new Number(parsedValue);
        }
        
        public int getValue() {
            return value;
        }
        
        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Number{");
            sb.append("value=")
              .append(value);
            sb.append('}');
            return sb.toString();
        }
    }
}

• 문제는 , 내가 원하는 타겟 숫자에 대해 제곱수를 어떻게 조합해야 최소로 값을 구성할 수 있는가에 대한 문제였다.

• 어떻게 답에 근접할 수 있을까?
  • 일단 다이나믹 프로그래밍으로 ..
  • 일단 작은 수 부터

    1 = > 1^2
    2 => 1^2 + 1^2
    3 => 1^2 + 1^2 + 1^2
    4 => 2^2
    5 => 2^2 + 1^2 ...
    6 => 2^2 + 1^2 + 1^2 ...

  • dp 배열 초기화
    • dp 배열을 사용해 각 숫자를 표현하는 데 필요한 제곱수의 최소 개수를 정의
    • 초기 배열값은 5로서, 문제 상황에서 나올 수 있는 제곱수의 최대 개수보다 큰 값으로 설정
  • 시작점 설정
    • dp[0] 은 0 으로 설정
    • 이 값은 뒤이어 계산되는 dp[i] 에서 활용
  • 주요 루프

    for (int i = 1; i <= naturalNumber.getValue(); i++) {
        for (int j = 1; j * j <= i; j++) {
            int square = j * j;
            dp[i] = Math.min(dp[i], dp[i - square] + 1);
        }
    }

    • dp 배열을 채우기 위하여 루프 사용
    • 각 숫자 i 에 대해 가능한 모든 제곱수 j*j 를 사용하여 dp[i] 의 값을 업데이트한다.
  • 최적화
    • dp[1], dp[2], dp[3] 등을 계산하는 방법은 이전 dp 값들과 연관이 있다.
    • 예를 들어, dp[5]를 계산할 때, dp[4]와 dp[1] 값들을 활용한다.
    • 이 값들은 이미 최적화된 값이므로, dp[5] 또한 최적화된 값

Uploaded by N2T