[LeetCode] 279. Perfect Squares

문제링크

숫자가 주어졌을 때, perfect square인 수들의 합으로 해당 숫자를 만들어야 하며, 이때 필요한 숫자의 최소 개수를 구하는 문제이다.

처음에는 해당 숫자보다 작지만 가장 큰 perfect square을 빼주는 식으로 풀려했다.
예를 들어 13의 경우 13-9 = 4, 4-4 =0 --> 2개 이런 식이다.
그렇지만 12의 경우 위처럼 풀면 12-9 = 3, 3-1=2, 2-1=1, 1-1=0 --> 4개이지만, 실제로 최소 개수는 4+4+4=12, 3개이다.

해당 문제를 풀기 위해 1부터 해당 숫자까지의 array에 해당 숫자를 만들기 위한 perfect square의 수를 저장해주었다.

예를 들어, 12가 주어졌다고 했을 때

1=1 -> 1개, 2=1+1 -> 2개, 3=1+1+1 -> 3개이다.

0	1	2	3	4	5	6	7	8	9	10	11	12
	1	2	3

4는 perfect square이므로 1개이며
5(4+1)는 arr[4] + min(arr[5-1], arr[5-4]) = 1 + min(arr[4], arr[1])으로 2개,
6(4 + 1 + 1)은 arr[4] + min(arr[6-1], arr[6-4]) = 1 + min(arr[5], arr[2])으로 3개,
7(4 + 1 + 1 +1)은 arr[4] + min(arr[7-1], arr[7-4]) = 1 + min(arr[6], arr[3])으로 4개,
8(4+4)은 arr[4] + min(arr[8-1], arr[8-4]) = 1 + min(arr[7] + arr[4]) = 2개이다.

이를 표로 정리하면 아래와 같다.

0	1	2	3	4	5	6	7	8	9	10	11	12
	1	2	3	1	2	3	4	2

9부터 12까지도 위와 같이 진행하면 아래와 같다.
9는 perfect square이므로 1개
10은 arr[9] + min(arr[9], arr[6], arr[1]) = 1 + 1 = 2개
11은 arr[9] + min(arr[10], arr[7], arr[2]) = 1 + 2 = 3개
12는 arr[9] + min(arr[11], arr[8], arr[3]) = 1 + 2 =3개

0	1	2	3	4	5	6	7	8	9	10	11	12
	1	2	3	1	2	3	4	2	1	2	3	3

따라서 위의 규칙을 정리하면 아래와 같다.

arr[i] = min(A[i-1], A[i-4], A[i-9], ...) + 1
= min(A[i-j*j]) + 1 where i-j*j>=0

코드로 정리하면 아래와 같다.

int arr[10001];

int numSquares(int n){
    
    int mul=2;

    for(int i=1;i<=n;i++)
    {
        if(i==1 || i==2 || i==3)
        {
            arr[i] = i;
            continue;
        }

        if(i>=(mul+1)*(mul+1)) mul+=1;
        if(i==mul*mul) {
            arr[i] = 1;
            continue;
        }
        int min=100000000;
        for(int j=1;j<=mul;j++)
        {
            if(arr[i-(j*j)]<min) min=arr[i-(j*j)];
        }
        arr[i]=min+1;
    }

    return arr[n];
}