[LeetCode] 1954. Minimum Garden Perimeter to Collect Enough Apples

https://leetcode.com/contest/weekly-contest-252/problems/minimum-garden-perimeter-to-collect-enough-apples/

Constraints:

• 1 <= neededApples <= 10^15

=> 수학공식을 써서 풀어야 시간 복잡도를 줄일 수 있는 문제.
등차수열의 합 공식 $n(n+1)/2$ 사용.

[python]

def minimumPerimeter(self, neededApples: int) -> int:
    n = 0
    while(n * (n + 1) * (2*n + 1) * 2 < neededApples):
        n += 1
    return n * 8

[C++]

long long minimumPerimeter(long long neededApples) {
    long n = 0;
    while(n * (n + 1) * (2 * n + 1) * 2 < neededApples)
        n++;

    return n * 8;
};

• 동일한 공식 동일한 원리로 풀었는데 파이썬과 C++ Runtime 차이 무엇?? 속도는 C가 깡패인듯...

• brute force 방식으로 간단히 풀수 있지만, 더 속도를 줄이고 싶으면 bineary search를 적용하면 된다.