백준 17626번 : Four Squaares [자바]

🧫 문제 분석

✔️ 출처

Four Squares 실버 3

 

📖 문제

DP문제

 

1~n-1까지의 four squares를 구하고 n의 four squares 를 구한다.

 

단순히 현재 자신의 최대 제곱근의 제곱을 자신의 수에서 뺀 나머지의 four squares를 이용하면 틀린다. 

 

12의 경우

최대 제곱근은 3이며 

12 - 9 = 3 이므로 dp[3] 의 값을 더해주면 dp[3] (3) + 3^3(1) = 4개  

로 최소가 된다 싶겠지만

 

2^2 + 2^2 + 2^2, 단 3개만으로 12를 완성할 수 있다. 

 

때문에 

해당 수의 1~최대 제곱근까지를 탐색해야한다.

 

점화식

dp[i] = Math.min(dp[i - (j*j)] + 1, dp[i])  [i = 2~N , j = 1 ~ sqrt(i)]

 

---

🔅 문제 풀이

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

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];
        dp[0] = 0;
     
        for (int i = 1; i * i <= n; i++) {
            dp[i*i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            if (dp[i] == 1) continue;
            
            // 해당 수의 1~제곱근까지의 수를 제곱하고 ( + 1) 나머지를 이전에 구했던 dp값에서 가져옴(dp[i-j*j])
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j <= Math.sqrt(i); j++) {
                dp[i] = Math.min(dp[i - (j * j)] + 1, dp[i]);
            }
        }

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

}

 

 

 

❗ 오답노트 / 필요한 지식

1. 여러 조합이 생길때는 모든 경우의 수를 따져보자