Lesson 10. Prime and composite numbers - MinPerimeterRectangle

1. 문제

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:
  int solution(int 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.

Write an efficient algorithm for the following assumptions:
  - N is an integer within the range [1..1,000,000,000].

 

넓이가 N인 직사각형 중, 최소 둘레를 구하는 문제.

 

직사각형의 넓이: \( A \times B \)

직사각형의 둘레: \( 2 \times (A + B) \)

 

예시) N = 30, return 22

변의 길이(A)	변의 길이(B)	둘레
1	30	62
2	15	34
3	10	26
5	6	22

 

 

2. 매개변수 제한

• 넓이(N): 1 ~ 1,000,000,000

 

3. 코드 (C++)

약수 구하기 알고리즘을 사용했다.

#include <limits>

int solution(int N) {

    int i = 1;
    int minimal_perimeter = numeric_limits<int>::max();

    //약수 찾기
    while(i * i < N)
    {
        if(N % i == 0)
        {
            int A = i;
            int B = N / i;
            int perimeter = 2 * (A + B);
            if(perimeter < minimal_perimeter) minimal_perimeter = perimeter;
        }
        i++;
    }

    if(i * i == N)
    {
        int perimeter = 4 * i;
        if(perimeter < minimal_perimeter) minimal_perimeter = perimeter;
    }

    return minimal_perimeter;
}