직사각형들의 두 변이 배열로 주어지고, 범위를 나타내는 변수 first와 last가 있다고 가정해 봅시다. 이때 목표는 변 길이의 비율(긴 변 ÷ 짧은 변)이 [first, last] 범위 안에 속하는 직사각형의 개수를 구하는 것입니다.
예제 1
입력
rec[] = { { 200, 210 }, { 100, 50 }, { 300, 190 }, { 180, 200 }, { 300, 200 } }, first = 1.0, last = 1.6
출력
변의 비율이 범위 [a, b] 내에 있는 직사각형의 개수: 4
설명
비율이 [1.0, 1.6] 범위에 속하는 변의 조합은 다음과 같습니다.
{200, 210}, {300, 190}, {180, 200}, {300, 200}
예제 2
입력
rec[] = { { 10, 20 }, { 30, 10 }, { 100, 500 }, { 900, 300 }, { 450, 90 } }, first = 3.0, last = 4.0
출력
변의 비율이 범위 [a, b] 내에 있는 직사각형의 개수: 2
설명
비율이 [3.0, 4.0] 범위에 속하는 변의 조합은 다음과 같습니다.
{30, 10}, {900, 300}
접근 방법
이 문제는 pair<int, int> 배열의 형태로 변의 정보를 입력받습니다. 각 쌍(pair)마다 큰 값 ÷ 작은 값으로 계산한 비율이 [first, last] 범위에 포함되는지 확인하고, 조건을 만족하면 카운트를 증가시키는 방식으로 해결할 수 있습니다. 전체 과정은 다음과 같습니다.
- pair<int, int> 타입의 배열 rec[]를 선언하여 직사각형의 두 변을 저장합니다.
- 비율 범위를 정의하기 위해 두 개의 변수 first와 last를 사용합니다.
- ratio_sides(pair<int, int> rec[], int total, double first, double last) 함수는 직사각형의 변들과 범위를 인자로 받아, 비율이 [a, b] 범위 내에 있는 직사각형의 개수를 반환합니다.
- 카운트 변수를 0으로 초기화합니다.
- for 반복문을 사용해 i = 0부터 i < total까지 배열을 순회합니다.
- 각 쌍에서 더 큰 값을 maxi = max(rec[i].first, rec[i].second)로 추출합니다.
- 더 작은 값을 mini = min(rec[i].first, rec[i].second)로 추출합니다.
- 두 값의 비율을 ratio = maxi / mini로 계산합니다.
- 계산된 비율이 [first, last] 범위 내에 있다면 카운트를 1 증가시킵니다.
- 반복문이 종료되면 최종 카운트를 결과로 반환합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
int ratio_sides(pair<int, int> rec[], int total, double first, double last){
int count = 0;
for (int i = 0; i < total; i++){
double maxi = max(rec[i].first, rec[i].second);
double mini = min(rec[i].first, rec[i].second);
double average = maxi/mini;
if (average >= first){
if(average <= last){
count++;
}
}
}
return count;
}
int main(){
pair<int, int> rec[] = { { 200, 210 }, { 100, 50 }, { 300, 190}, {180, 200}, {300, 200}};
int total = 5;
double first = 1.0, last = 1.6;
cout<<"변의 비율이 범위 [a, b] 내에 있는 직사각형의 개수: "<<ratio_sides(rec, total, first, last);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
변의 비율이 범위 [a, b] 내에 있는 직사각형의 개수: 4
마무리
이 알고리즘은 각 직사각형을 한 번씩만 확인하면 되므로 시간 복잡도는 O(N)입니다. 여기서 N은 직사각형의 개수입니다. max와 min 함수를 활용해 어떤 변이 더 긴지 미리 정렬할 필요 없이 항상 '큰 값 ÷ 작은 값' 형태로 비율을 계산할 수 있다는 점이 이 풀이의 핵심입니다.