[백준/JAVA] 17626번: Four Squares

📖 문제

17626번: Four Squares

 

 

💡  풀이 방식

• DP

규칙을 찾아 점화식을 채운다.

1 : 1^2                                           ⇒ 1개

2 : 1^2 + 1^2                               ⇒ 2개

3 : 1^2 + 1^2 + 1^2                   ⇒ 3개

4 : 2^2                                           ⇒ 1개

5 : 2^2 + 1^2                               ⇒ 2개

6 : 2^2 + 1^2 + 1^2                   ⇒ 3개

7 : 2^2 + 1^2 + 1^2 + 1^2       ⇒ 4개

8 : 2^2 + 2^2                               ⇒ 2개

9 : 3^2                                           ⇒ 1개

 

규칙은

제곱수가 갱신될 때까지는 이전 dp 값에서 +1을 해 주는 것

그러면 아래와 같은 점화식을 세울 수 있다.

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

 

i의 범위는 2부터 N까지,

j의 범위는 i부터 j의 제곱근까지이며

완전탐색을 통해 i보다 작은 제곱수에서 뺀 dp[i - j * j] 中 최솟값 + 1해 배열을 채우면 된다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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 배열 초기화
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;    // dp[0]이 꼭 0이어야 함
        dp[1] = 1;
        
        for(int i = 2 ; i <= N ; i++) {
            for(int j = 1 ; j * j <= i ; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        System.out.println(dp[N]);
    }
}
 

 

 

---

💦 어려웠던 점

처음에 제곱인 경우는 먼저 처리하고,  dp 식을 세웠었는데 잘못된 식을 작성해서 자꾸 틀렸다,, 

패턴 찾는 게 참 어렵당,ㅠ

 

1회독	2회독	3회독	4회독	5회독
V	240528	240630

 

---

(참고)

[백준] 17626번 : Four Squares – JAVA [자바]

[백준 17626번 / Java] Four Squares - DP

[BOJ] 백준 17626번 Four Squares (Java)

 

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