MinPerimeterRectangle

🔗 문제 링크

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/min_perimeter_rectangle/start/

❔ 문제 설명

An integer N is given, representing the area of some rectangle.

The area of a rectangle whose sides are of length A and B is A B, and the perimeter is 2 (A + B).

The goal is to find the minimal perimeter of any rectangle whose area equals N. The sides of this rectangle should be only integers.

For example, given integer N = 30, rectangles of area 30 are:

(1, 30), with a perimeter of 62,
(2, 15), with a perimeter of 34,
(3, 10), with a perimeter of 26,
(5, 6), with a perimeter of 22.

Write a function:

def solution(N)

that, given an integer N, returns the minimal perimeter of any rectangle whose area is exactly equal to N.

For example, given an integer N = 30, the function should return 22, as explained above.

⚠️ 제한사항

• N is an integer within the range [1..1,000,000,000].

---

💡 풀이 (언어 : Python)

쉽게 풀었다. 전 약수 개수 구하기의 응용문제였다. 똑같이 루트 n크기 만큼 for문을 돌면서 perimeter의 값을 구해주고 최소값을 갱신하는 알고리즘이다. 시간복잡도는 $O(N)$

import math

def solution(N):
    minimum = 1000000000 * 4

    for n in range(1, int(math.sqrt(N)) + 1):
        if N % n == 0:
            perimeter = 0
            if n ** 2 == N:
                perimeter = (2 * n) * 2
            else:
                perimeter = (n + (N // n)) * 2

            if perimeter < minimum:
                minimum = perimeter

    return minimum