정수 배열이 주어졌을 때, 두 원소를 더했을 때 같은 합이 되는 쌍(pair)이 가장 많이 나타나는 경우를 찾아야 합니다. 즉, 배열에서 만들 수 있는 모든 쌍의 합을 계산한 뒤, 동일한 합이 가장 자주 등장하는 횟수를 구하는 것이 이 문제의 목표입니다.
입력 예시 1
Arr[]= { 1,2,3,4,2 }
출력 결과
동일한 합을 갖는 쌍의 최대 개수 : 3
설명 — 배열에서 만들 수 있는 모든 쌍의 합은 다음과 같습니다.
{1,2}, {1,2} → 합:3
{1,3},{2,2} → 합:4
{1,4},{2,3},{3,2} → 합:5
{2,4} → 합:6
{3,4} → 합:7
합이 5인 경우가 3개로 가장 많습니다.
입력 예시 2
Arr[]= { 5,3,6,1 }
출력 결과
동일한 합을 갖는 쌍의 최대 개수 : 1
설명 — 이번에는 중복되는 합이 없습니다.
{5,3} → 합:8
{5,6} → 합:11
{5,1} → 합:6
{3,6} → 합:9
{3,1} → 합:4
{6,1} → 합:7
모든 쌍의 합이 서로 다르므로 최대 개수는 1입니다.
풀이 접근 방법
정수 배열 Arr[]에 정수들을 저장합니다.
정수 변수 size는 배열의 길이를 나타냅니다.
함수 countEqualSum(int arr[], int n)은 배열과 그 크기를 입력받아, 동일한 합을 생성하는 쌍의 최대 개수를 반환합니다.
먼저 각 합의 빈도(등장 횟수)를 저장할 sum 배열을 준비합니다.
모든 쌍 (i, j)에 대해 두 원소의 합을 계산하고, 해당 인덱스의 카운트를 1씩 증가시킵니다.
sum 배열의 각 인덱스는 "어떤 쌍의 합"을 의미하고, 그 값은 해당 합이 등장한 횟수를 의미합니다.
sum 배열 전체를 탐색하여 가장 큰 값을 찾아 maxC에 저장합니다.
maxC를 결과로 반환합니다.
모든 쌍을 한 번씩 검사해야 하므로 시간 복잡도는 O(n²)입니다. 여기서는 편의상 최대 합이 20을 넘지 않는다고 가정하고 크기 20의 배열을 사용했지만, 실전에서는 unordered_map을 활용하면 음수나 매우 큰 값이 포함된 입력에도 유연하게 대응할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 동일한 합을 갖는 쌍의 최대 개수를 반환하는 함수
int countEqualSum(int arr[], int n){
int sum[20]={0};
int maxC = 0;
// 모든 쌍의 합에 대한 빈도수 저장
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++){
sum[ arr[i]+arr[j] ]++;
}
// 빈도수 중 최댓값 탐색
for(int i=0;i<20;i++)
if(sum[i]>maxC)
maxC=sum[i];
return maxC;
}
int main(){
int Arr[] = { 1,2,3,4,2 };
int size = 5;
cout << "Maximum count of pairs which generate the same sum : "
<< countEqualSum(Arr, size);
return 0;
}
실행 결과
Maximum count of pairs which generate the same sum : 3
마무리
이 문제의 핵심 아이디어는 합 자체를 배열의 인덱스로 활용하는 것입니다. 모든 쌍의 합을 빈도 테이블에 누적한 뒤, 그중 최댓값만 골라내면 간단히 해결됩니다. 고정 크기 배열 대신 맵(map) 기반 자료구조를 사용하면 입력 범위에 제약 없이 확장할 수 있으니, 상황에 맞게 선택해 보세요.