가장 효율적인건 근의 공식을 이용하는 것이지만, 그보다는 좀더 알고리즘적으로 효율적인 접근이 있어 공유해 드립니다.
좀 더 효율적인 풀이법은 이분 탐색을 이용하는 것입니다. 세로 길이를 x, 가로 길이를 y 라고 하였을때(x <= y),
둘레와 넓이를 생각하면 x + y = brown//2 + 2 이고 x * y = brown + yellow 라는 것을 알 수 있습니다.
여기서 x + y = brown//2 + 2 로 고정되기 때문에 x와 y를 적절히 잘 선택해서 그 곱이 brown + yellow가 되도록 하면 되는데, 이 때 x와 y의 차가 더 작을 수록 그 곱은 커진다는 성질을 이용하면 됩니다.
여기서 s = brown//2 + 2 라고 하면 x는 1 ~ s//2 의 범위를 가지게 되고, 이를 통해 y = s - x로 x * y의 값을 구할 수 있습니다.
우리가 구해야하는 곱을 m = brown + yellow이라 하면 x * y 가 m 보다 크면 x는 더 작아져야 하고(x와 y의 차가 더 커져야 그 곱이 작아지기 때문), 반대로 x * y가 m보다 작으면 x는 더 커져야 합니다.
따라서 1 ~ s//2 의 범위에서 x를 찾을때 x * y의 값을 보고 x가 더 커져야 하는지 작아져야 하는지 알수 있게 되는데, 이때 이분탐색으로 찾으면 효율적으로 찾을 수 있습니다.
이렇게 찾으면 O(log brown)이기 때문에 yellow의 약수를 찾는 O(root(yellow)) 보다 효율적입니다.(brown은 최대 5000, yellow는 최대 2000000)
감사합니다 :)
👍
인정! 탐색과정이 좀 더 프로그래밍답네요, 근데 log brown 임은 어떻게 계산되나요?