[백준] DP - 1699번 제곱수의 합(다른 풀이 봄)

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

문) 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

---

풀이

1. 테이블 정의 : dp[i] = i를 구성하는 최소 항의 개수

2. 점화식

• 제곱수인 경우, dp[i] = 1;
• 그 외, dp[i] = Math.min(dp[i], dp[j] + dp[i-j]);

3. 초기값 : dp[0] = 0; dp[1] = 1;

 

<점화식 도출>

dp[1]~dp[10] 까지 해당하는 값을 쭉 나열해 보았다.

**dp[]는 편의상 생략함.
1 = 1²
2 = 1² + 1²
3 = 1² + 1² + 1²
4 = 2²
5 = 2² + 1²
6 = 2² + 1 + 1
7 = 2² + 1 + 1 + 1
8 = 2² + 2² 
9 = 3² 
10 = 3² + 1

 

다시 정리해보면, 이렇게 작성할 수 있다.

 

dp[10] = dp[1]+dp[9] = 2 ✅

         = dp[2]+dp[8] = 4 ...

 

제일 처음 값을 말도 안 되는 큰 값을 배정해두고,

현재 i값이 제곱수일 때와 아닌 경우의 수를 나누어 식을 작성하면 된다.

 

스스로 생각했을 때 어디까지 했나? (망한 풀이입니다.)

중첩 for문을 활용하여, n - (i*i) 반복하는 과정을 구상.

 

먼저 제곱수의 조건을 생각했다.

1) n > (i * i) 를 만족시킨 값.

2) 1의 조건식을 만족시키는 수 중 n에 가까운 수부터 for문을 돌림.

 

그러다보니 제곱수의 조건이 한도 끝도 없고 말도 안 되는 조건식을 달아야 했음.

dp는 값을 누적하여 효율적이게 계산하는 것이 특징인데, 전혀 효율적이지도 않았음.

결국, 풀이를 봤을 때 그나마 쓸만한 구상은 n값에서 뺀다 정도...?

 

코드

import java.io.*;
public class Main {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        dp[0] = 0;
        dp[1] = 1;
        for (int i=2; i<=n; i++) {
            dp[i] = 99999;
            for(int j=1; j<=i/2; j++) {
                //자기가 제곱수인 경우
                if(j*j == i) {
                    dp[i] = 1; break;
                } else {
                    dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
                }
            }
        }
        br.close();
        bw.write(String.valueOf(dp[n]));
        bw.flush();
        bw.close();
    }
}

---

솔직히 여러모로 자괴감이 많이 들었다.

dp문제를 계속 풀었다하나, 처음 보는 유형이면 다시 원점으로 돌아가는 것 같다.

분하기도 하고, 스스로의 멍청함에 개탄하기도 한다.

 

그래도 어떡하나...

알고리즘은 많이 풀어보고 꾸준히 생각한 사람에게 유리하다는 마음으로 지속해 나가자고 다짐한다.

 

[참고] https://jainn.tistory.com/274

https://soojong.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-1699%EB%B2%88-%EC%A0%9C%EA%B3%B1%EC%88%98%EC%9D%98-%ED%95%A9