[C] LeetCode 279. Perfect Squares

문제

번역

정수 n이 주어졌을때, n을 만들 수 있는 가장 적은 perfect squares 수의 개수를 구해라.

perfect squares 란 어떤 정수의 제곱이 되는 정수를 말한다.

예를 들어 1,4,9,16은 perfect squares 이지만, 3과 11은 아니다.

접근 방법 및 소스 코드

일단 어떤 숫자 i에 대해서, 이 수를 만들 수 있는 가장 적은 perfect squares 수의 최악의 경우는 1로만 이루어진 경우이다.

즉, 숫자 i를 만들기 위해 1을 i번 쓰는 것이 가장 최악이다.

 

그 다음, i라는 숫자를 만들기 위해 어떤 제곱수 하나를 더 더한다고 생각해보자.

k라는 제곱수가 있다고 해보자.

k<=i 인 모든 k에 대해서 i-k에다가 k를 더해서 i를 만드는 경우를 DP를 통해서 구하면 된다.

그 중 가장 작은 값을 저장하면 된다.

 

int dp[10005];
int min(int a, int b) { return (a>b)?b:a;}
int numSquares(int n) {
    dp[0]=0;
    dp[1]=1;
    dp[2]=2;
    dp[3]=3;
    dp[4]=1;

    for(int i=5;i<=n;i++) {
        dp[i]=i;
        for(int j=1;  j*j<=i;j++) {
            dp[i] = min(dp[i], dp[i-j*j] + 1);
        }
    }

    return dp[n];
}