279. Perfect Squares

1. 문제

1-1. 원문

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

1 <= n <= 104

1-2. 내용 번역

숫자 n이 주어진다. 제곱수의 합들로 n을 구성할 때, 가장 적은 제곱수의 개수를 구해라.

2. 문제 이해

2-1. 내용 이해

내용은 크게 어렵지 않다. 제곱수는 1, 4, 9, 16, 25, ... 를 말하는 것이고 n이 제곱수의 합들로 이루어지게 한다는 것은, n이 12일 때는 9+1+1+1 로 이루어지게 하던지, 4+4+4로 이루어지게 하던지, 4+4+1+1+1+1로 이루어지게 하던지 등의 구성을 생각해 보면 된다. 여기서 4+4+4가 3개의 제곱수로 12를 표현할 수 있기 때문에 가장 적은 제곱수의 개수가 되고, 따라서 n이 12일 때의 리턴값은 3이다.

2-2. 접근법 생각

Knapsack 알고리즘을 공부하고 있기 때문인지 모르겠지만, knapsack에 너무나 꼭 맞는 문제라고 생각한다. 배낭의 총 무게는 n, 배낭에 담는 물체의 무게는 제곱수, 담아도 되고 안담아도 되고, 담으면 그만큼 배낭에 담을 수 있는 무게는 줄어든다. 라고 치환해서 생각할 수 있으니까. 낭비없이 모두 담았을 때 물체의 최소 개수를 구하면 된다.

2-3. 적용한 풀이

Knapsack은 DP로 memoization을 하기 위해 보통은 2D array를 만들어서 해결하고, 1D array로 해결 가능한 경우도 꽤 많다. 이 array의 행과 열 혹은 행에 어떠한 라벨을 붙이는지가 관건이 된다.

어떤 문제는 topdown으로 생각하면 편하고 어떤 문제는 bottomup으로 생각해야 편하다. 그 조건이 어떤것인지는 아직 잘 모르겠다...

Knapsack Topdown (Recursion)

Knapsack을 자연스럽게 생각하면 topdown 방식을 먼저 떠올리게 된다. 그런데 topdown을 적용하게 되면 배열의 라벨에 붙이는 조건을 잘 따져봐야 한다. 마이너스가 인덱스가 되는 경우도 있고, n+1로 만들어서 0또한 고려해야 할 수도 아닐수도 있기 때문이다.

Knapsack BottomUp (Tabulation)

1부터 n까지 차례로 해를 구해간다. bottomup은 구현은 간단하지만 개인적으로 topdown을 bottomup으로 생각하기 어려운 부분이 많다.

3. 구현

Knapsack

class Solution {
    val UNVISITED = 20000

    fun numSquares(n: Int): Int {
        // return bottomUp(n)
        return topDown(n)
    }

    fun bottomUp(n: Int): Int {
        val memo = IntArray(n+1){0}

        for(i in 1..n) {
            var min = Integer.MAX_VALUE
            var j = 1
            while(i >= j*j) {
                min = Math.min(memo[i-(j*j)]+1, min)
                j++
            }
            memo[i]=min
        }

        return memo[n]
    }

    fun topDown(n: Int): Int {
        val memo = IntArray(n+1){UNVISITED}
        memo[0] = 0

        return topDownDP(n, memo)
    }

    fun topDownDP(n: Int, memo: IntArray): Int {
        if (n == 0) return 0
        if (memo[n] != UNVISITED) return memo[n]

        var i = 1
        while(n >= i*i) {
            memo[n] = Math.min(memo[n], topDownDP(n-(i*i), memo)+1)
            i++
        }

        return memo[n]
    }
}

4. 복잡도

시간 복잡도: O(N∗Sqrt(N))
공간 복잡도: N