N×N 크기의 행렬이 주어졌을 때, j번째 열의 원소 합이 i번째 행의 원소 합보다 큰 모든 유효한 인덱스 쌍 (i, j)의 개수를 구하는 것이 목표입니다.
이 문제는 행렬을 한 번씩 순회하면서 각 행과 열의 원소 합을 미리 계산해 둔 뒤, 가능한 모든 쌍을 비교하는 방식으로 해결할 수 있습니다.
구체적인 절차는 다음과 같습니다.
- 각 행의 원소 합은
rowsum[N]배열에 저장합니다. - 각 열의 원소 합은
colsum[N]배열에 저장합니다. rowsum[i]와colsum[j]로 만들 수 있는 모든 쌍을 검사하여colsum[j] > rowsum[i]를 만족하면 카운트를 1씩 증가시킵니다.
예제로 이해하기
입력 예시 1
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 rowsum[i] < colsum[j]를 만족하는 쌍 (i, j): (0,0), (0,1), (0,3), (2,0), (2,1), (2,3), (3,0), (3,1), (3,3)
입력 예시 2
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 모든 행의 합과 열의 합이 같으므로 조건을 만족하는 쌍은 존재하지 않습니다.
알고리즘 접근 방식
- 정수형 2차원 배열
Arr[]에 임의의 값들을 초기화하여 준비합니다. - 배열(행렬)의 크기를 저장할 변수
n을 선언합니다. countPairs(int arr[][3], int n)함수는 행렬과 그 크기를 입력으로 받아, 주어진 조건을 만족하는 유효한 쌍의 개수를 반환합니다.- 행의 합을 저장할
rowsum[n]배열과 열의 합을 저장할colsum[n]배열을 0으로 초기화하여 선언합니다. - 이중 반복문으로 행렬을 순회하면서
arr[i][j]값을rowsum[i]와colsum[j]에 각각 누적하여 i행과 j열의 합을 계산합니다. - 다시 두 개의 반복문으로
colsum[]과rowsum[]의 모든 조합을 비교합니다. colsum[j] > rowsum[i]인 경우마다 카운트를 증가시킵니다.- 최종적으로 카운트를 결과로 반환합니다.
이 알고리즘의 시간 복잡도는 행 합·열 합 계산에 O(N²), 쌍 비교에 O(N²)이 소요되므로 전체적으로 O(N²)입니다. 추가로 사용되는 배열 공간은 O(N)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[][3], int n){
// 유효한 쌍의 개수
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
입력 행렬 { {1,3,5}, {2,4,6}, {3,5,7} }에서 각 행의 합은 9, 12, 15이고 각 열의 합은 6, 12, 18입니다. 이때 열의 합이 행의 합보다 큰 쌍은 총 4개가 존재합니다.