백준 17626 자바 - Four Squares

// Four Squares
package Silver_III_3;

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

public class Ex17626 {
    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];
        dp[1] = 1; // 1*1
        
        for (int i = 2; i <= n; i++) {
            int min = Integer.MAX_VALUE;

            for (int j = 1; j * j <= i; j++) {
                int temp = i - j * j;
                min = Math.min(min, dp[temp]); // 제곱수의 최소 개수
            }

            dp[i] = min + 1;
        }

        System.out.println(dp[n]);
    }
}

 

이번 문제는 아래 블로그를 보고 풀었다.

[BOJ] 백준 17626번 : Four Squares (JAVA) (tistory.com)

[BOJ] 백준 17626번 : Four Squares (JAVA)

처음엔 위 블로그의 주의 사항처럼 큰 수부터 제곱수를 구했지만, 최소한의 개수를 만족하지 못 했다.

아직은 dp가 어렵지만, 비슷한 유형의 문제가 많으니 하다보면 익숙해질 것이다.