[LeetCode] 279. Perfect Squares

 

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

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Perfect Squares

문제 유형 : 수학, 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

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.

 

정수 n이 주어진다. 합이 n이되는 완전제곱수의 최소 개수를 구하시오.

 

풀이

우선, n보다 작은 완전제곱수만 올 수 있으므로, 1부터 sqrt(n)까지의 제곱수들을 따로 배열에 저장시킨다.

dp배열을 만들어서 dp[i] = 합이 i가 되는 최소 완전제곱수의 개수로 한다.

 

12를 예시로 들면, 4+4+4가 가장 적은 수들로 이루어짐을 알 수 있다.

dp[8](4+4)에서 1개만 늘어난 것임을 알 수 있다.

 

제곱수들을 담은 배열을 squares라고 할 때,

dp[i] = min(dp[i], dp[i-squares[j]] + 1)이라는 점화식을 세울 수 있다.

이전에 만들어진 수들에서 추가로 완전제곱수들을 얹어서 최소 수를 만들어보는 것이다.

dp[n]에는 최소의 개수가 들어있다.

 

코드

C++

class Solution {
public:
    int numSquares(int n) {
        vector<int> squares;
        vector<int> dp(n+1, 1e9);
        // base case
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 1; i <= int(sqrt(n)); i++) {
            squares.push_back(i*i); // {1, 4, 9 ... }
        }

        for(int i = 2; i <= n; i++) {
            for(int j = 0; j < squares.size(); j++) {
                if(i-squares[j] < 0) break; // 이전 수가 더 없으면 그만두기
                dp[i] = min(dp[i], dp[i-squares[j]] + 1);
            }
        }

        return dp[n];
    }
};

 

 

Go

func numSquares(n int) int {
    dp := make([]int, n+1)
    squares := []int{}

    dp[0] = 0
    dp[1] = 1

    for i := 1; i <= int(math.Sqrt(float64(n))); i++ {
        squares = append(squares, i*i)
    }

    for i := 2; i <= n; i++ {
        dp[i] = 1e9
        for j := 0; j < len(squares); j++ {
            if i-squares[j] < 0 {
                break
            }
            dp[i] = getMin(dp[i], dp[i-squares[j]]+1)
        }
    }

    return dp[n]
}

func getMin(a, b int) int {
    if a < b {
        return a
    }
    return b
}