[백준, 자바, 17626번] Four Squares

풀이

• 해당 문제는 최소 개수의 제곱수로 임의의 값을 찾는 문제로
• 어떻게 해결해야할지 고민을 한 결과, 
• 임의의 값의 sqrt까지 모든 제곱수를 구한 다음
• 재귀로 모든 경우를 찾아보자라고 결정함.
• 다만 0.5초라는 시간 제한이 있었기에, 뭔가 뭔가 했지만 그냥 해봄
• 그런데 처음에 그냥 무의식적으로 visit 체크를 해서
• 중복하여 같은 것을 더하지 못하도록 함.
• 그래서 계속 87퍼쯤에서 멈추길래
• 이후엔 방문체크를 하지 않고 해결하게 됨.
• 그리고 중간에는 계속 끝에서부터 처음까지 탐색하도록 했어서
• 시간초과가 발생하길래, 현재 위치부터 조회하도록 하여
• 시간 효율을 줄여 해결할 수 있었음.

 

import java.io.*;
import java.util.*;
public class _17626 {
    static List<Integer> li = new ArrayList<>();
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        result = 50000;
        addZegob(N);
        findRec(0,N, li.size()-1);
        System.out.println(result);
    }

    private static void addZegob(int N) {
        for (int i=1; i<=(int)Math.sqrt(N); i++) li.add(i*i);
    }

    private static void findRec(int cnt, int hap, int idx) {
        if (hap==0) {
            if (result>cnt) result = cnt;
        }
        else if (result>cnt){
            for (int i=idx; i>=0; i--) {
                if (hap-li.get(i)>=0) findRec(cnt+1,hap-li.get(i), i);
            }
        }
    }
}