문제 개요
n개의 양수로 구성된 배열이 주어집니다. 우리의 목표는 arr[i] * arr[j] > arr[i] + arr[j] 조건을 만족하는 순서쌍 (i, j)의 개수를 세는 것입니다. 단, 인덱스는 0 ≤ i < j < n을 만족해야 하며, 여기서 n은 배열에 포함된 원소의 개수입니다.
가장 직관적인 방법은 두 개의 for 루프를 중첩하여 배열의 모든 가능한 쌍을 탐색하는 것입니다. 각 쌍에 대해 arr[i]와 arr[j]의 합과 곱을 계산한 뒤, 곱이 합보다 크면 카운트를 증가시킵니다.
예시를 통해 자세히 살펴보겠습니다.
입력 − Arr[] = { 1, 1, 2, 3 }, N = 4
출력 − 유효한 쌍의 개수 − 1
설명 − 유일하게 조건을 만족하는 쌍은 (2, 3)입니다.
2*3=6 > 2+3=5
입력 − Arr[] = { 2, 2, 2 }, N = 3
출력 − 유효한 쌍의 개수 − 0
설명 − 2*2와 2+2는 모두 4로 같기 때문에, 곱이 합보다 큰 쌍은 존재하지 않습니다.
프로그램에서 사용하는 접근 방식
- 양수로 초기화된 정수 배열 arr[]를 준비합니다.
- 배열 Arr[]의 길이를 저장할 변수 n을 선언합니다.
- countPairs(int arr[], int n) 함수는 배열과 그 길이를 입력으로 받아, 곱이 합보다 큰 쌍의 개수를 반환합니다.
- 두 개의 중첩된 for 루프를 사용하여 배열의 각 쌍을 탐색합니다.
- 외부 루프는 0 ≤ i < n-1 범위로, 내부 루프는 i < j < n 범위로 실행됩니다.
- arr[i] * arr[j] > arr[i] + arr[j] 조건을 검사하고, 참이면 count를 1 증가시킵니다.
- 모든 루프가 종료되면 count에는 곱이 합보다 큰 쌍의 총 개수가 저장되어 있습니다.
- 최종적으로 count를 결과값으로 반환합니다.
참고로 이 알고리즘은 모든 쌍을 한 번씩 검사하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 매우 클 경우에는 수학적 성질(예: 두 수가 모두 2 이상이고 적어도 하나가 3 이상일 때만 곱이 합보다 커짐)을 활용해 최적화할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
int count = 0;
int sum = 0;
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(arr[i] * arr[j] > arr[i] + arr[j]) // 조건 검사
{ count++; }
}
}
return count;
}
int main(){
int arr[] = { 1, 2, 3, 2 };
int len = sizeof(arr) / sizeof(int);
cout << "Count of number of pairs :" << countPairs(arr, len);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of number of pairs :2
예제 배열 { 1, 2, 3, 2 }에서 조건을 만족하는 쌍은 (2, 3)과 (3, 2), 즉 값 기준으로 2×3=6 > 2+3=5를 만족하는 두 개의 쌍이므로 결과는 2가 됩니다.