leetcode 1954. Minimum Garden Perimeter to Collect Enough Apples

문제 링크 :https://leetcode.com/problems/minimum-garden-perimeter-to-collect-enough-apples/

<문제 해석>

2d 좌표계의 모든 정수 좌표점 (i,j) 에는 |i| + |j|개의 사과가 있다.

원점을 중심으로 하고 x,y축과 평행인 정사각형안의 사과들을 가져갈 수 있을 때 neededApples만큼의 사과를 가져갈 수 있는 정사각형의 둘레값의 최소값을 구하는 문제이다.

 

<풀이>

일단 정사각형의 한변의 길이는 짝수여야 한다. 변의 길이가 홀수인 정사각형의 꼭지점은 어차피 정수 좌표점에 있지 못하기 때문에 둘레의 최소값을 구하려면 짝수여야 한다.

구체적인 풀이는 다음과 같다.

먼저 정사각형이 커질수록 가질 수 있는 사과의 수가 어떻게 변하는지 규칙을 찾아야 한다.

위의 이미지는 정사각형이 커짐에 따라 각 정수좌표점의 사과 개수를 나타낸 것이다. 각 정사각형은 둘레의 길이가 각각 2, 4, 6 ... 과 같은 식이다. 여기서는 파란색으로 박스친 부분의 갯수만 구해보겠다. 어차피 저걸 4배로 하면 전체 사과 개수가 된다. 정사각형의 각 변의 가운데점((1,0), (2,0), (3,0) ...)을 중심으로 규칙성을 찾아보면

첫번째 정사각형은 1 + 2

두번째 정사각형은 2 + 2*3 + 4

세번째 정사각형은 3 + 2*4 + 2*5 + 6

.

.

.

과 같이 된다.

정사각형의 각 변의 가운데 점의 x값을 k라 하면 파란색 부분의 사과 개수는

k + 2(k+1) + 2(k+2) + ... + 2(2k - 1) + 2k 이다. 이를 식으로 나타내면

3k + \(\sum_{i=1}^{k-1} (k+i)\) 가 되고 이를 계산하면 \(3k^{2}\) 이다. 이걸 4배 해줘야 하므로 최종적으로 각 사각형의 둘레에 있는 사과의 개수는 \(12k^{2}\)이다.

이건 둘레에 있는 개수이고 안쪽에 있는 사과들까지 전부 더해줘야 한다. 이 경우 \(\sum_{i=1}^{k} (12i^2)\)을 계산해주면 되고 \(4k^{3} + 6k^{2} + 2k\)를 얻게 된다.

이제 neededApples < \(4k^{3} + 6k^{2} + 2k\)를 만족하는 k의 최소값을 찾고 여기에 8을 곱하면(k의 8배가 둘레길이임) 정답이 된다.

여기서는 이진탐색으로 풀 수 있다.

neededApples의 range가 제한되어 있으므로 이진탐색으로 풀 수 있다. 코드는 다음과 같다.

class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        lo = 1
        hi = 7e4
        
        while lo < hi:
            mid = (lo + hi)//2
            num_apples = 4*mid**3 + 6*mid**2 + 2*mid
            
            if num_apples < neededApples:
                lo = mid+1
            
            elif num_apples >= neededApples:
                hi = mid
        
        return int(lo*8)

hi는 neededApples의 최대값인 \(10^{15}\)에 대해서 \(10^{15}\) < \(4k^{3} + 6k^{2} + 2k\)인 k로 해주면 된다. 다만 hi가 크면 search range도 커지므로 위의 식을 만족하면서 적당히 작은걸로 해주면 좋다.