크기가 NXN인 행렬이 제공됩니다. 목표는 j열의 요소 합이 i행 요소의 합보다 크도록 모든 유효한 인덱스 쌍(i,j)의 개수를 찾는 것입니다.
행렬을 순회하고 각 행과 열의 요소 합계를 계산하여 이를 수행합니다.
각 요소의 합을 rowsum[N]에 저장하고 각 열의 요소 합을 colsum[N]에 저장합니다.
이제 rowsum[i]와 colsum[j]의 쌍을 만들고 colsum[j]>rowsum[i]인지 확인합니다. true인 경우 이러한 쌍에 대해 카운트를 증가시킵니다.
예를 들어 이해합시다.
Input-: matrix= {
{ 1,2,0,1},
{ 3,3,0,2},
{ 1,3,0,2},
{ 3,0,0,2}
}; 출력 − 유효한 쌍의 수 − 9
설명 -
Rowsum[0]= 1+2+0+1=5 Colsum[0]= 1+3+1+3=8 Rowsum[1]=3+3+0+2=8 Colsum[1]= 2+3+3+0=8 Rowsum[2]= 1+3+0+2=6 Colsum[2]= 0+0+0+0=0 Rowsum[3]=3+0+0+2=5 Colsum[3]= 1+2+2+2=7 Pairs of (i,j) such that rowsum[i] < colsum[j]. (0,0), (0,1), (0,3), (2,0), (2,1), (2,3), (3,0) (3,1), (3,3)
입력 -
Arr[]= { {1,1,1}, {1,1,1}, {1,1,1} } N=3 출력 − 유효한 쌍의 수 − 0
설명 -
Rowsum[0]= 1+1+1=3 Colsum[0]= 1+1+1=3 Rowsum[1]= 1+1+1=3 Colsum[1]= 1+1+1=3 Rowsum[2]= 1+1+1=3 Colsum[2]= 1+1+1=3 No pairs possible where rowsum[i]<colsum[j]에서 쌍이 불가능합니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
임의의 숫자로 초기화된 정수 배열 Arr[]을 사용합니다.
-
Arr[]의 길이를 저장하는 변수 n을 사용합니다.
-
countPairs(int arr[], int n) 함수는 배열의 길이를 입력으로 받아 유효하고 원하는 조건을 충족하는 쌍을 반환합니다.
-
우리는 두 개의 배열 rowsum[n]과 colsum[n]을 사용합니다.
-
행렬을 순회하고 rowsum[i] 및 colsum[j]에 arr[i][j]를 추가하여 행 i와 열 j의 합을 계산합니다.
-
이제 두 개의 for 루프를 사용하여 배열 colsum[] 및 rowsum[]을 탐색합니다.
-
colsum[j]>rowsum[i]인 경우. 증분 수.
-
카운트를 결과로 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[][3], int n){
// Count of pairs
int count = 0;
int rowsum[n]={0};
int colsum[n]={0};
int i,j;
for (i = 0; i < n; i++){
for (j = 0; j < n; j++){
rowsum[i]+=arr[i][j];
colsum[j]+=arr[i][j];
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++)
if(colsum[j]>rowsum[i])
{ count++; }
}
return count;
}
int main(){
int Arr[][3] = { {1,3,5},{2,4,6},{3,5,7} };
int side=3;
cout <<endl<<"Count of number of pairs : "<< countPairs(Arr, side);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of number of pairs : 4