C++로 목표 면적에 맞는 사각형 구성하기

특정한 직사각형 웹 페이지 면적이 주어졌다고 가정해 봅시다. 우리의 과제는 다음 세 가지 조건을 모두 만족하는 길이 L과 너비 W를 가진 직사각형 웹 페이지를 설계하는 것입니다.

• 웹 페이지의 면적은 주어진 목표 면적과 정확히 같아야 합니다.
• 너비 W는 길이 L보다 클 수 없습니다. 즉, 항상 L >= W를 만족해야 합니다.
• L과 W의 차이는 가능한 한 최소가 되어야 합니다.

예를 들어 입력값이 4라면 출력은 [2,2]가 됩니다. 목표 면적이 4일 때 가능한 조합은 [1,4], [2,2], [4,1] 세 가지입니다. 두 번째 조건에 따라 [1,4]는 유효하지 않고, 세 번째 조건에 따르면 [4,1]은 [2,2]보다 적합하지 않습니다. 따라서 길이 L은 2, 너비 W는 2가 됩니다.

문제 해결 접근 방법

이 문제는 제곱근부터 시작하여 아래로 내려가며 약수를 찾는 방식으로 효율적으로 해결할 수 있습니다. 면적의 제곱근에 가장 가까운 약수를 찾으면 L과 W의 차이가 자연스럽게 최소화되기 때문입니다. 구체적인 단계는 다음과 같습니다.

• i를 면적(area)의 제곱근으로 초기화하고, i > 0인 동안 i를 1씩 감소시키며 반복합니다.
  • 만약 area를 i로 나눈 나머지가 0이라면(즉, i가 area의 약수라면):
    • 벡터 v를 선언하고 {area/i, i}를 삽입합니다.
    • v를 반환합니다.
• 반복문이 끝날 때까지 적절한 값을 찾지 못하면 {-1, -1}을 반환합니다.

예제 코드

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> constructRectangle(int area) {
      for (int i = sqrt(area); i > 0; i--) {
         if (area % i == 0) {
            vector<int> v{ area / i, i };
            return v;
         }
      }
      return { -1, -1 };
   }
};
main(){
   Solution ob;
   print_vector(ob.constructRectangle(4));
}

입력

4

출력

[2, 2]

이 코드는 시간 복잡도 O(√N)으로 동작합니다. 제곱근부터 시작하기 때문에 첫 번째로 발견되는 약수 쌍이 곧 길이와 너비의 차이가 가장 작은 조합이 되므로, 추가적인 비교나 정렬 없이 바로 결과를 얻을 수 있다는 점이 이 알고리즘의 핵심 장점입니다.