백준 1699 제곱수의 합(Java)

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

1699번: 제곱수의 합

---

 

해석 및 팁

 

---

 

이 문제는 백준 17626 Four Squares 문제와 같은 문제입니다. 이문제도 다이나믹프로그래밍으로 풀어야 하는데  점화식은 dp [N] = min(dp[N], dp[N - 제곱수] + dp[제곱수]) 일댸 dp[제곱수] = 1 이므로 dp[N - 제곱수]만 구해주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

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

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

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

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