길이가 n인 정수 배열 Arr[]가 주어졌을 때, 임의의 두 수의 합이 나머지 한 수와 같아지는 삼중항 (Arr[i], Arr[j], Arr[k])의 개수를 구하는 것이 이 문제의 목표입니다.
조건식은 a + b = c 형태이며, 여기서 a, b, c는 배열 Arr[]의 요소이고 인덱스 i, j, k는 0 ≤ i < j < k < n을 만족해야 합니다.
이 문제는 세 개의 for 반복문을 사용해 해결할 수 있습니다. arr[x] + arr[y] = arr[z]를 만족하면서 x ≠ y ≠ z인 경우 count 값을 증가시키면 됩니다. 예제를 통해 자세히 살펴보겠습니다.
입력 예제
arr[] = { 1, 2, 2, 3, 4 }, N = 5출력
삼중항의 개수: 4
설명
두 수의 합이 세 번째 수와 같은 삼중항은 다음과 같습니다.
Arr[] = [ 1, 2, 2, 3, 4 ] → (1, 2, 3) : 1 + 2 = 3
Arr[] = [ 1, 2, 2, 3, 4 ] → (1, 2, 3) : 1 + 2 = 3
Arr[] = [ 1, 2, 2, 3, 4 ] → (1, 3, 4) : 1 + 3 = 4
Arr[] = [ 1, 2, 2, 3, 4 ] → (2, 2, 4) : 2 + 2 = 4
총 삼중항 개수: 4개
입력 예제 2
arr[] = { 2, 2, 2, 2, 2 }, N = 5출력
삼중항의 개수: 0
설명
배열의 모든 요소가 2이므로 임의의 두 수의 합은 항상 4가 되지만, 세 번째 수는 2에 불과합니다. 따라서 조건을 만족하는 삼중항은 하나도 없습니다.
총 삼중항 개수: 0개
알고리즘 접근 방법
- 임의의 정수 값으로 초기화된 정수 배열 Arr[]를 준비합니다.
- 변수 N에는 배열 Arr[]의 길이가 저장됩니다.
- 함수 countTriplets(int arr[], int n)는 배열과 그 길이를 매개변수로 받아, 한 수가 나머지 두 수의 합으로 표현될 수 있는 삼중항의 개수를 반환합니다.
- 삼중항의 개수를 저장할 변수 count를 0으로 초기화합니다.
- 세 개의 for 반복문을 사용하여 삼중항의 각 요소를 순회합니다.
- 가장 바깥쪽 반복문은 0 ≤ i < n-2, 중간 반복문은 i < j < n-1, 가장 안쪽 반복문은 j < k < n 범위로 실행됩니다.
- arr[i] + arr[j] == arr[k] 또는 arr[i] + arr[k] == arr[j] 또는 arr[k] + arr[j] == arr[i] 조건을 검사하고, 참이면 count를 증가시킵니다.
- 모든 반복문이 종료되면 count에는 조건을 만족하는 삼중항의 총 개수가 저장됩니다.
- count 값을 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[], int n){
int count = 0;
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++){
if(arr[i]+arr[j]==arr[k] || arr[j]+arr[k]==arr[i] || arr[k]+arr[i]==arr[j]){
count++;
}
}
}
}
return count;
}
int main(){
int Arr[]={ 1,2,2,3,4 };
int N=5; //length of array
cout <<endl<< "Number of triplets : "<<countTriplets(Arr,N);
return 0;
}
실행 결과
Number of triplets : 4