백준 17626 Four Squares(Java)

https://www.acmicpc.net/problem/17626

17626번: Four Squares

---

 

해석 및 팁

 

---

 

이 문제의 핵심은 dp [i] = dp [i- j*j] + dp [j*j]이라는 점화식을 발견하는 것입니다.  이때 dp [j*j]는 제곱수이므로 항상 1입니다. 따라서 dp [i- j*j]의 최솟값을 구한 후 1을 더해주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int min;
    int n = sc.nextInt();
    int arr[] = new int[n + 1];

    arr[1] = 1;

    for(int i = 2; i <= n; i++) {
      min = 50000;
      for(int j = 1; j * j <= i; j++) {
        min = Math.min(min, arr[i - j * j]);
      }
      arr[i] = min +1 ;  //min + arr[j * j]
    }

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