BJ17626 Four Squares

·2022년 5월 11일
0

백준 알고리즘

목록 보기
32/34

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();
		
	}
}
profile
SSAFY 7기

0개의 댓글