[DP+Math] 백준 17626번 Four Squares - JAVA

 

내 수준은 딱 골드 5인 것 같아서

요즘은 알고리즘 스터디 문제 중 실버 ~ 골드5 문제를 열심히 풀고 있다.

 

오늘은 맞춘 문제이지만, 내가 취약해하는 요소 DP + Math

2개가 모두 섞여있어서 복습을 해보고자 한다.

 

 

---

1. 출처

---

https://www.acmicpc.net/problem/17626

17626번: Four Squares

 

• 모든 자연수는 최대 4개의 제곱수의 합로 나타낼 수 있음
• 26 = 5^2 + 1^2 혹은 4^2 + 3^2 + 1^2 이런식
• 최소 개수의 제곱수의 합으로 나타낼 수 있는 경우를 찾는 문제

 

 

---

2. 설계

---

 

시간 제한이 0.5초이다 보니 저절로 DP가 떠올랐다. 그렇다면 공식이 있을 것이다.

내가 공식을 찾아내는 방법은 무지성 1부터 해보는 것이다 ㅋㅋ

 

1 -> 1^2
2 -> 1^2 + 1^2
3 -> 1^2 + 1^2 + 1^2

4 -> 2^2
5 -> 2^2 + 1^2
6 -> 2^2 + 1^2 + 1^2
7 -> 2^2 + 1^2 + 1^2 + 1^2
8 -> 2^2 + 2^2

9 -> 3^2
10 -> 3^2 + 1^2
11 -> 3^2 + 1^2+ 1^2
12 -> 3^2 + 1^2 + 1^2 + 1^2
13 -> 3^2 + 2^2
14 -> 3^2 + 2^2 + 1^2
15 -> 3^2 + 2^2 + 1^2 + 1^2

16 -> 4^2

 

16까지 했을 때 확실하게 법칙을 알아낼 수 있었다.

• 제곱수는 최소개수가 1개이다.
• 새로운 제곱수가 등장하면 다음수는 제곱수를 사용한다.
  • 그러니까 예를들어 8이면, 현재 새롭게 나타난 제곱수 2^2 = 4를 쓴다.
  • 그럼 나머지 8-4=4에 대해 이미 계산되어 있는 dp[4]를 이용한다.
  • 즉, dp[8-4] + 1 = 2가 되는 것이다. (제곱수는 갯수가 언제나 1이기 때문)

 

 

그런데 위 설계대로만 하면 예제 3번 11339를 입력했을 때 답이 3으로 나오지 않는다.

 

11339와 가장 가까운 제곱수는 106이다. (106^2 = 11236)

그럼, 나머지 수 103을 dp에서 찾아주면 되는데, (11236(106^2) + 103 = 11339)

dp[103] = 10^2 + 1^2 + 1^2 + 1^2이여서

dp[11339] = 5가 되어버린다.

최대 4가지의 제곱수 합으로 나타낼 수 있다고 했는데, 가정에서 틀려버리는 것이다.

 

 

그래서 나는 앞의 제곱수를 하나 줄여보았다.

11025(105^2) + 314 = 11339이다.

다행히 dp[314] = 2였다.

그래서 답이 3이 나오게 되는 것이다.

 

여기서 알아낼 수 있었던 것은 바로 직전에 나오는 제곱수를 사용하는게 아니라

1~현재 나온 제곱수를 모두 따져봐야한다는 것이다.

 

 

그러니까 정리를 해보자면,

• 제곱수는 최소개수가 1개이다.
• 1~직전에 나온 제곱수를 모두 써서 최소갯수의 제곱수 합을 찾는다.

 

 

---

3. 전체 코드

---

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        int[] dp = new int[N+1];
        dp[1] = 1;

        int pointer = 1; //몇의 제곱수인가?, 직전 제곱수 저장
        for(int i=2; i<=N; i++){
            if((int)Math.pow(pointer+1,2)==i){
                pointer++; //직전 제곱수 증가
                dp[i] = 1;
                continue;
            }
            
            dp[i] = dp[i - pointer*pointer]+1; //0이면 정답은 항상 0이 나오므로 초기값 계산
            for(int j=pointer-1; j>=1; j--){
                dp[i] = Math.min(dp[i], dp[i - j*j]+1);
            }
        }

        System.out.println(dp[N]);

    }
}

 

 

과거에는 예제의 답이 나오면 컴파일을 돌려보곤 했는데,

요즘은 설계부터 제대로해서 내가 예제까지 만들어 돌린 다음에 답을 체크해보니 단번에 맞는다.

뿌듯하다~ : )