[백준/17626] Four Squares - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버3
출처 : 백준 - Four Squares

🦧 문제 풀이 접근

dp를 이용한다.
숫자중 제곱수는 미리 1의 값을 넣어둔다.
1부터 N까지 반복하면서 i가 1인 경우는 continue를 한다.
그 외에는 for문으로 각 제곱수 + N-제곱수를 탐색하여 최소값을 찾는다.

💻 code

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

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

🥇 결과

🎓 느낀점

처음에는 두번째 for문에서 1부터 N/2까지 모든 경우를 다 확인했더니 시간 초과가 나왔다.
두번째 for문을 N이 아닌 logN으로 돌려서 문제를 해결했다.
O(N^2)에서 O(NlogN)으로 개선했다.