숫자로 이루어진 배열 Arr[]가 주어졌을 때, 세 원소의 곱이 가능한 모든 삼중항 중 최솟값과 일치하는 삼중항의 개수를 구하는 것이 목표입니다. 단, 인덱스 조건 i<j<k를 만족하면서 arr[i]*arr[j]*arr[k]가 최소가 되는 경우를 셉니다.
해결 방법은 다음과 같습니다. 먼저 i<j<k 조건을 만족하는 가장 작은 곱을 찾아 minprod에 저장한 뒤, 곱이 minprod와 같은 모든 삼중항의 개수를 계산합니다.
예시를 통한 이해
입력 − arr[] = { 1,2,3,2,4,1,5 }
출력 − 삼중항의 개수 − 2
설명 −
최소 곱은 2입니다.
삼중항 1 [ 1,2,3,2,4,1,5 ] → (1,2,1), 곱 = 2
삼중항 2 [ 1,2,3,2,4,1,5 ] → (1,2,1), 곱 = 2
곱이 최솟값 2인 삼중항은 총 2개입니다.
입력 − arr[] = { 1,1,2,1,2,2 }
출력 − 삼중항의 개수 − 1
설명 −
최소 곱은 1입니다.
삼중항 1 [ 1,1,2,1,2,2 ] → (1,1,1), 곱 = 1
곱이 최솟값 1인 삼중항은 총 1개입니다.
프로그램의 접근 방식
임의의 숫자로 초기화된 정수 배열 Arr[]를 준비합니다.
배열 Arr[]의 길이를 저장할 변수 N을 선언합니다.
함수 countTriplets(int arr[], int n)는 배열과 그 길이를 입력으로 받아, 최소 곱과 같은 곱을 가지는 삼중항의 개수를 반환합니다.
삼중항의 개수를 저장할 변수 count를 0으로 초기화합니다.
각 삼중항의 곱을 저장할 변수 prod를 1로 초기화합니다.
모든 삼중항 중 최소 곱을 저장할 변수 minprod를 9999로 초기화합니다. 즉, 배열에서 나올 수 있는 어떤 곱보다 큰 값으로 시작합니다.
삼중항의 각 원소를 선택하기 위해 3개의 for 루프로 배열을 순회합니다.
가장 바깥쪽 루프는 0<=i<n-2, 안쪽 루프는 i<j<n-1, 가장 안쪽 루프는 j<k<n 범위를 탐색합니다.
prod = arr[i]*arr[j]*arr[k]를 계산하고, prod<=minprod이면 minprod를 prod로 갱신합니다.
첫 번째 순회가 끝나면 minprod에는 모든 삼중항 곱 중 최솟값이 저장됩니다.
이후 동일한 3중 for 루프로 배열을 한 번 더 순회합니다.
prod==minprod이면 count를 증가시킵니다. 해당 삼중항이 최소 곱을 가지기 때문입니다.
모든 루프가 종료되면 count에는 조건을 만족하는 삼중항의 총 개수가 저장됩니다.
count를 결과로 반환합니다.
이 알고리즘은 3중 루프를 두 번 사용하므로 시간 복잡도는 O(n³)입니다.
예제
#include <bits/stdc++.h>
using namespace std;
// 최소 곱을 가지는 삼중항의 개수를 세는 함수
int countTriplets(int arr[], int n){
int count = 0;
int prod = 1;
int minprod = 9999; // 배열 내 어떤 곱보다 큰 값으로 최솟값 초기화
// 첫 번째 순회: 최소 곱 찾기
for (int i = 0; i < n-2; i++){
for (int j = i+1; j < n-1; j++){
for (int k = j+1; k < n; k++){
prod = arr[i]*arr[j]*arr[k];
if ( prod <= minprod )
{ minprod = prod; }
}
}
}
// cout<<"minproduct :"<<minprod; // 최소 곱 출력용
// 두 번째 순회: 최소 곱과 같은 삼중항 개수 세기
for (int i = 0; i < n-2; i++){
for (int j = i+1; j < n-1; j++){
for (int k = j+1; k < n; k++){
prod = arr[i]*arr[j]*arr[k];
if ( prod == minprod ){
count++;
//cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]<<" c :"<<arr[k]; // 삼중항 출력용
}
}
}
}
return count;
}
int main(){
int Arr[]={ 1,2,3,1,2,6};
int N=5; // 배열 길이
cout <<endl<< "Number of triplets : "<<countTriplets(Arr,N);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 생성됩니다 −
Number of triplets : 2