leetcode 279, Perfect Squares

들어가는 말

n을 나타낼 수 있는 제곱수 합의 최소 갯수를 구하는 문제다. 처음에는 1부터 전부 해보려고 했는데(브루트포스) 범위가 10^4라는 걸 보고 관뒀다. 대신 dp로 풀어야 겠다고 생각했다.

dp로 풀 때는 언제나 1부터 주어진 수로 다가간다고 생각해야 한다. 이미 구해 놓은 것들을 어떻게 조합해서 주어진 수를 만들 수 있을까로 생각해야 한다. 제일 좋은 방법은 1부터 어느정도까지 손으로 직접 써보는 거다.
1, 1 -> 1
2, 1+1 -> 2
3, 1+1+1 -> 3
4, 4 -> 1
5, 4+1 -> 2
6, 4+2 -> 3
...
이렇게 s+(n-s)라는 걸 알아냈다.

코드 설명

n이 12라고 하자.
그렇다면 12는 3의 제곱수 9와 3의 합이라고 할 수 있다.
그러면 3은 1+1+1로 나타낼 수 있다.
그러므로 12를 제곱수의 합으로 나타낸다면 9+1+1+1이렇게 되는 것이다.

그러면 n보다 작은 최대 제곱수만을 구해서 나머지는 dp로 구하면 되는 거 아닐까?
여기가 내가 빠졌던 함정이다.
아니. n보다 작은 최대 제곱수를 이용하는 것보다 더 좋은 방법이 있을지도 모른다.
12는 '9+1+1+1'로도 가능하지만 '4+4+4'도 가능하다.
즉, n보다 작은 모든 제곱수의 경우의 수를 구해서 최소값을 넣어야 적절한 답인 것이다.

class Solution {
    public int numSquares(int n) {
        //dp 문제는 주어진 숫자를 어떻게 최소한의 방법으로 구성하는지
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        //sq의 제곱은 n보다 큰 최소의 제곱 수
        int sq = (int)Math.sqrt(n)+1;
        int[] sq_num = new int[sq];
        for(int i=1; i<sq; i++){
            sq_num[i] = i*i;
        }

        System.out.println(sq);

        for(int i=1; i<=n; i++){
            for(int j=1; j<sq; j++){
                //제곱한 수가 주어진 i보다 커서 해당 제곱수를 포함하지 못한다.
                if(i < sq_num[j]){
                    break;
                }
                dp[i] = Math.min(dp[i], dp[i - sq_num[j]]+1);
            }
        }

        return dp[n];

    }
}

1. 먼저 n을 포함한 dp의 배열을 최대값으로 초기화한 후 인덱스 0에는 0을 넣어준다. 조심해야 할 건 먼저 최대값으로 초기화를 해줘야 한다는 거다.
2. 해당수 n보다 큰 최소 제곱수 sq를 구한다. 그리고 범위가 1부터 sq-1까지 해당 인덱스의 제곱수를 넣어준다.
3. 그리고 i를 1부터 n까지 돌리면서 dp에 최소 수를 넣어준다. j는 제곱수의 범위인데 만일 제곱수가 구하려는 i보다 큰 경우는 break를 해서 다음 i로 넘어가게 한다. 만일 제곱수가 i보다 작으면 현재의 dp[i]와 해당 제곱수를 포함했을 때의 i갯수를 구해서(dp[i - sq_num[j]]+1, 제곱수는 1이고 주어진 n을 제곱수로 체우고 나머지 숫자를 구하는 방법은 dp[i - sq_num[j]]이다) 최소값을 구하면 된다.

여담

dp는 어려워~ 규칙만 찾으면 되지만, 규칙 찾기가 쉽지 않다.