[leetcode] 279. Perfect Squares

문제

https://leetcode.com/problems/perfect-squares/

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.

숫자를 주어지면 제곱수들로 덧셈을 하여 최소 개수를 구하여라.

---

풀이

보자마자 0-1 배낭 문제 풀이가 떠올랐다.
배낭 문제에 대해 잘 정리된 블로그를 첨부한다.
https://jeonyeohun.tistory.com/86

1. [1..n] 범위의 제곱수들로 이루어진 배열을 만든다.
2. 2차원 배열 dp에 첫 행을 열 인덱스로 초기화한다.
3. dp를 열 우선 순회 하면서 01 배낭 알고리즘으로 업데이트해준다.

코드

class Solution {
    public int numSquares(int n) {
        //create num_list
        List<Integer> numList = new ArrayList<>();
        //add number
        for(int i = 1; i*i <= n ; i++){
            numList.add(i*i);
        }
        //0 1 배낭 
        int dp[][] = new int[numList.size()][n+1];
        dp[0][0] = 0 ;
        dp[0][1] = 1;
        
        //배열 초기화 
        for(int j = 0; j < n+1 ; j++)
            dp[0][j] = j;
        
        for(int i = 1; i< numList.size() ;i ++){
            for(int j = 1 ; j <n+1 ;j++ )  {
                if(numList.get(i) <= j){
                    dp[i][j] = Math.min(dp[i-1][j] , dp[i][j-numList.get(i)]+1);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }          
        }
        return dp[numList.size()-1][n];
    }
}