직사각형의 넓이가 입력으로 주어졌을 때, 길이와 너비의 차이가 최소가 되도록 하는 두 변의 길이를 구하는 것이 이 문제의 핵심입니다.
사각형의 넓이 = 길이 × 너비
예시
입력 − 넓이 = 100
출력 − 차이가 최소인 사각형의 변:
길이 = 10, 너비 = 10
설명 − 넓이가 100이 되는 변의 조합으로는 2-50, 4-25, 5-20, 10-10이 있습니다. 이 중 차이가 최소인 조합은 10-10이며, 그 차이는 0입니다. 정사각형은 모든 변의 길이가 같은 특별한 형태의 직사각형이라는 점을 기억해두면 이해하기 쉽습니다.
입력 − 넓이 = 254
출력 − 차이가 최소인 사각형의 변:
길이 = 127, 너비 = 2
설명 − 넓이 254를 만들 수 있는 변의 조합 중에서 차이가 최소가 되는 유일한 조합은 127과 2입니다.
접근 방법
이 프로그램에서 사용하는 전략은 다음과 같습니다. 먼저 넓이의 제곱근 값을 구한 뒤, 그 값부터 1까지 내림차순으로 탐색하면서 곱이 입력된 넓이와 같고 차이가 최소인 두 값을 찾습니다. 제곱근 근처에서 시작하는 이유는 두 수의 차이가 가장 작아지려면 두 수가 서로 가까워야 하기 때문이며, 이 덕분에 시간 복잡도를 O(√N) 수준으로 줄일 수 있습니다.
정수 변수 Area에 넓이를 입력받습니다.
함수 rectangleSides(int area1)는 area1을 받아 길이와 너비의 차이가 가능한 한 최소가 되는 사각형의 두 변을 출력합니다.
정수형 변수 length, breadth, tmp1을 선언합니다.
tmp1 = ceil(sqrt(area1))로 설정합니다.
for 루프(int i = tmp1; i > 0; i--)를 사용해 역순으로 탐색합니다.
(area1 % i == 0)이 참이면 length = area1 / i, breadth = i로 설정합니다.
break 문으로 반복을 종료합니다.
구한 길이와 너비를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void rectangleSides(int area1){
int length, breadth;
int tmp1 = ceil(sqrt(area1));
for (int i = tmp1; i > 0; i--) {
if (area1 % i == 0) {
length = ceil(area1 / i);
breadth = i;
break;
}
}
cout<<"Sides of Rectangle with minimum difference :"<<endl;
cout << "Length = " << length << ", Breadth = " << breadth << endl;
}
int main(){
int Area = 140;
rectangleSides(Area);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Sides of Rectangle with minimum difference : Length = 14, Breadth = 10