.leetcode(279. Perfect Squares)

문제

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

문제 풀기 전

1. 이런 문제는 앞에서 접근할지, 뒤에서 접근할지 결정해야하는데 숫자가 커짐에 따라 앞에 숫자를 알고 있으면 계산이 빨라질 수 있으니 이건 앞에서부터 세야한다.
2. 이렇게 앞에것이 뒤에 결과에 도움을 주면 보통 dp로 풀리니 그 점도 염두하면 좋다.

직접 푼 풀이

소요시간: 42분(07:07 ~ 07:49)

class Solution {
    public int numSquares(int n) {
        int[] box = new int[n+1];

        int index = 1;
        for(int i=1; i<n+1; i++) {
            if (i >= Math.pow(index, 2)) {
                index++;
            }


            int min = Integer.MAX_VALUE;
            for(int j=index; j>=1; j--) {
                int count = 0;
                int num = i;
                int temp = j;
                int psn = (int)Math.pow(temp, 2);
                while(true) {
                    if (num == 0) {
                        box[i] = count;
                        break;
                    }

                    if (box[num] != 0 && num != i) {
                        box[i] = box[num] + count;
                        break;
                    }

                    if (num < psn) {
                        temp--;
                        psn = (int)Math.pow(temp, 2);
                        continue;
                    }

                    num -= psn;
                    count++;
                }
                min = Math.min(min, box[i]);
            }
            box[i] = min;

        }
        return box[n];
    }
}

느낀점

1. 좋은 풀이는 아니다. 배열을 쓰긴했지만 거의 Brute Force로 볼 수 있다.
2. 솔루션으로는 dp, greedy, 수학적인 방법이 있다. 간단히 얘기해보면 dp는 위의 로직을 좀 더 효율적으로 고치면 된다. greedy는 count중심의 풀이다. dp가 점진적으로 count를 찾아간다면 greedy는 count를 정해놓고 맞아 아니야를 결정해서 풀이를 이어나간다. 수학적인 방법은 공식이 있는데 다음에 더 이해해보기로 한다.
3. 일단 dp로 풀이된 내용을 더한다.

누적되는 알고리즘 접근 설명서

class Solution {
    public int numSquares(int n) {

        int limit = (int)Math.sqrt(n) + 1;
        int[] perfectSqureNumbers = new int[limit];
        for (int i=0; i<limit; i++) {
            perfectSqureNumbers[i] = (i+1) * (i+1);
        }

        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0]=0;
        for (int i=1; i<=n; i++) {
            for (int each: perfectSqureNumbers) {
                if (i >= each) {
                    dp[i] = Math.min(dp[i-each]+1, dp[i]);
                }
            }
        }

        return dp[n];
    }
}

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• dp로 풀기
• greedy로 풀기
• 수학적 개념 다시 보기