백준 17626번: Four Squares

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

모든 자연수는 넷 이하의 제곱수의 합으로 나타낼 수 있다.

주어진 N이 최소 몇개의 제곱수의 합으로 표현하는 문제이다.

 

일단, 자연수가 몇개의 제곱수로 이루어져있는지 기록하는 배열을 만든다.

    다음으로, 받은 N이 제곱수인지 아닌지 확인을 한다.

이는 sqrt(N) - (int)sqrt(N) == 0.0 인지 비교해보면 된다.

이 부분은 재귀함수에서 남아서 지속적으로 제곱수인지 아닌지를 판명하고 맞다면 1을 저장해준다.

 

제곱수가 아니라면 sqrt(N)부터 내려오면서 N의 경우의 수를 확인해준다.

    N을 이루는 제곱수는 필연적으로 sqrt(N)보다 같거나 작을 테니 sqrt(N)을 초기값으로 했다.

그 뒤로 여러 경우의 수를 구해보며 그 중에서 가장 작은 수를 배열에 저장해준다.

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

public class Main {
  static int[] cases = new int[50001];
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    int N = Integer.parseInt(br.readLine());

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(fSquare(N) + "");
    bw.flush();
    bw.close();
  }

  static int fSquare(int N) {
    
    if (cases[N] == 0) {
      cases[N] = 4;
      double rt = Math.sqrt(N);
      if (rt - (int)rt == 0.0) cases[N] = 1;
      else {
        for (int i = (int)rt; i > 0; i--) {
          int case1 = 1 + fSquare(N - (int)Math.pow(i, 2));
          cases[N] = case1 < cases[N] ? case1 : cases[N];
        }
      }
    }
    
    return cases[N];
  }
}