백준 17626번 : Four Squares(Java)

🔗 문제 링크

17626번: Four Squares

 

---

📖 풀이 과정

- 다이나믹 프로그래밍 유형의 문제입니다.
- 자연수 n을 최소 개수의 제곱수 합의 개수로 표현하면 다음과 같습니다.
  - 1 -> 1
  - 2 -> 2
  - 3 -> 3
  - 4 -> 1
  - 5 -> 2
  - 6 -> 3
  - 7 -> 4
  - 8 -> 1
  - 9 -> 1
  - 10 -> 2
  - 11 -> 3
  - 12 -> 4
  - 13 -> 5
  - 14 -> 6
  - 15 -> 7
  - 16 -> 1
- 이를 통해 점화식을 이끌어 낼 수 있습니다. 
- f(n) = f(n - m * m ) + 1
  - 이 식을 구현하는게 문제를 중요 부분이자, 어렵다고 생각합니다.
- 이러한 식을 이용해 반복문을 구현해 최솟값을 dp 배열에 할당하면 됩니다.

 

---

💻 코드

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

public class Main {
    static int[] dp;
    static int n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        dp = new int[n+1];
        solve();
        System.out.println(dp[n]);
    }
    
    public static void solve(){
       dp[1] = 1;
       for(int i = 2; i< n + 1; i++){
           dp[i] = Integer.MAX_VALUE;
           for(int j = 1; j * j <= i; j++){
               int temp = i - j * j;
               dp[i] = Math.min(dp[i], dp[temp] + 1);
           }
       }
    }
}