[Codility] 10.3 MinPerimeterRectangle

MinPerimeterRectangle 문제 풀기

직사각형의 가로와 세로가 $A$, $B$라 하면, 이 직사각형의 둘레(perimeter)는 $2 \times (A+B)$이다.
직사각형의 넓이가 $N$일 때, 직사각형의 둘레의 최솟값은? (단, 직사각형의 가로과 세로는 정수다.)

가로, 세로가 실수라면 고등학교 수학때 배운 산술-기하 평균을 이용할 수 있지만 정수이다.
$N = A \times B$이고 $A, B$가 정수이므로 $N$의 약수를 관찰하면 풀 수 있다.
약수를 구할 때 $\sqrt{N}$까지만 확인하면 된다.
(예를 들어, $100$의 약수를 구할 때, $10 \times 10 = 100$이므로 11 부터 확인할 필요가 없다.)

def solution(N):
    m = int(N ** 0.5) + 1
    
    # N이 소수/합성수 상관없이 N = 1*N은 항상 성립한다
    min_perimeter = 2 * (1 + N)
    for i in range(1, m):
        if N % i == 0:
            min_perimeter = min(min_perimeter, 2 *(i + N // i))

    return min_perimeter