https://www.acmicpc.net/problem/17626
간단한 재귀함수 구현 문제이고, 가지치기를 통해 불필요한 호출을 줄이면 된다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class FourSquares {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static int cnt_min = Integer.MAX_VALUE;
static void func (int num, int cnt) {
if(cnt >= cnt_min) return;
if(num == 0) {
cnt_min = Math.min(cnt, cnt_min);
return;
}
int sqrt = (int)Math.sqrt(num);
for(int i = sqrt; i >= sqrt / 2; i--) {
func(num - i * i, cnt + 1);
}
}
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
func(N, 0);
bw.append(cnt_min + "\n");
bw.flush();
}
}