0%

[백준/1699] 제곱수의 합

작성일 Edited on In Disqus:

Baekjoon Online Judge - 1699

Review

  • 무조건 큰 제곱수로 곱해서 구하는 것이 답이 아니다. 따라서 주어진 수를 구할 수 있는 모든 제곱수로 구해 본 다음 최소값을 찾으면 된다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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