이 글에서는 C++을 이용해 직각삼각형을 형성할 수 있는 빗변과 넓이 쌍의 개수를 구하는 방법을 알아보겠습니다.
주어진 문제는 빗변 H와 넓이 A로 이루어진 모든 가능한 쌍 (H, A) 중에서, 실제로 직각삼각형을 만들 수 있는 쌍의 개수를 세는 것입니다.
문제의 수학적 배경
먼저 기호를 정리하면 다음과 같습니다.
- x : 직각삼각형의 밑변
- y : 직각삼각형의 높이
- H : 직각삼각형의 빗변
직각삼각형의 넓이 공식은 다음과 같습니다.
A = (x × y) / 2
양변을 정리하면,
4 × A² = (x × y)² …… (1)
또한 피타고라스 정리에 의해,
x² + y² = H² …… (2)
(1)식과 (2)식을 연립하여 풀면,
4 × A² = x²(H² − x²)
이 식은 x²에 대한 이차방정식입니다. 실수 x가 존재하려면 판별식 D ≥ 0을 만족해야 하며, 이를 정리하면 다음 조건을 얻습니다.
H² ≥ 4 × A (직각삼각형이 존재하기 위한 조건)
즉, 어떤 쌍 (H, A)가 위 부등식을 만족하면 해당 빗변과 넓이로 직각삼각형을 만들 수 있습니다.
입력 및 출력 예시
입력 : 배열 H[ ] = { 3, 6, 8 }, A[ ] = { 2, 31, 12 }
출력 : 4
설명 : 가능한 (H, A) 쌍은 (3, 2), (6, 2), (8, 2), (8, 12) 입니다.
입력 : 배열 H[ ] = { 2, 5, 9 }, A[ ] = { 3, 11, 7 }
출력 : 4
설명 : 가능한 (H, A) 쌍은 (5, 3), (9, 3), (9, 11), (9, 7) 입니다.해결 방법
이제 두 가지 방법으로 문제를 해결해 보겠습니다.
1. 브루트 포스(완전 탐색) 접근법
가장 단순한 방법은 모든 가능한 (H, A) 쌍을 생성하고, 각 쌍이 H² ≥ 4 × A 조건을 만족하는지 확인한 뒤, 조건을 통과하는 쌍의 개수를 세는 것입니다.
코드 예시
#include <iostream>
using namespace std;
int main(){
int H[] = { 2, 5, 9 }; // 빗변 배열
int s1 = sizeof(H)/sizeof(H[0]);
int A[] = { 3, 11, 7 }; // 넓이 배열
int s2 = sizeof(A)/sizeof(A[0]);
int count = 0; // 카운트 초기화
// 모든 가능한 쌍 탐색
for (int i = 0; i < s1; i++) {
for (int j = 0; j < s2; j++) {
// 현재 쌍이 조건을 만족하는지 검사
if (H[i] * H[i] >= 4 * A[j]){
count++;
}
}
}
cout << "가능한 (H, A) 쌍의 개수: " << count;
return 0;
}
실행 결과
가능한 (H, A) 쌍의 개수: 4
코드 설명
위 코드에서는 중첩 반복문을 사용해 모든 (H, A) 쌍을 생성하고, 조건을 만족하는 경우 count 변수를 증가시킵니다. 이 코드의 시간 복잡도는 O(n²)로, 입력 크기가 커지면 비효율적입니다. 그렇다면 더 효율적인 두 번째 방법을 살펴보겠습니다.
2. 효율적인 접근법 (정렬 + 이진 탐색)
이 방법에서는 먼저 두 배열을 오름차순으로 정렬합니다. 그다음 각 빗변 길이에 대해 H² ≥ 4 × A를 만족하는 최대 넓이를 이진 탐색으로 찾습니다.
코드 예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int H[] = { 2, 5, 9 };
int s1 = sizeof(H) / sizeof(H[0]);
int A[] = { 3, 11, 7 };
int s2 = sizeof(A) / sizeof(A[0]);
int count = 0;
// 두 배열 정렬
sort(H, H + s1);
sort(A, A + s2);
int temp = -1;
for (int i = 0; i < s1; i++){
// 각 빗변 길이마다 이진 탐색 적용
int flag1 = 0;
int flag2 = s2 - 1;
while (flag1 <= flag2){
int mid = flag1 + (flag2 - flag1) / 2;
if ((H[i] * H[i]) >= (4 * A[mid])){
temp = mid;
flag1 = mid + 1;
}
else{
flag2 = mid - 1;
}
}
if (temp != -1){ // 가능한 넓이가 존재하는지 확인
count += temp + 1;
}
}
cout << "가능한 (H, A) 쌍의 개수: " << count;
return 0;
}
실행 결과
가능한 (H, A) 쌍의 개수: 4
코드 설명
위 코드는 먼저 두 배열을 오름차순으로 정렬한 후, 각 빗변 길이마다 이진 탐색을 수행하여 조건을 만족하는 최대 넓이의 위치를 찾습니다.
예를 들어 넓이 배열 A[ ]에서 인덱스 3의 위치에서 최대 넓이를 찾았다면, 그보다 작은 인덱스의 넓이들도 모두 조건을 만족하므로 한 번의 탐색으로 여러 개의 유효한 쌍을 동시에 셀 수 있습니다. 덕분에 불필요한 비교를 크게 줄일 수 있습니다.
마무리
이번 글에서는 직각삼각형을 만들 수 있는 빗변과 넓이 쌍의 개수를 구하는 문제를 다루었습니다. 시간 복잡도 O(n²)의 브루트 포스 방법과, 정렬 및 이진 탐색을 활용해 O(s1 log s2)로 개선된 효율적인 방법 두 가지를 살펴보았습니다. 입력 데이터가 클수록 후자의 접근법이 훨씬 유리하다는 점을 기억해 두시면 좋습니다. 이 글이 도움이 되었기를 바랍니다.