문제 개요
N개의 요소로 구성된 배열 Arr[]이 주어졌을 때, 서로 다른 인덱스(i ≠ j)를 가진 두 요소로 이루어진 모든 쌍 (Arr[i], Arr[j]) 중에서 그 합이 완전제곱수(perfect square)가 되는 쌍의 개수를 구하는 것이 목표입니다. 즉, Arr[i] + Arr[j]의 값이 어떤 정수의 제곱과 일치하는지 확인해야 합니다.
가장 직관적인 방법은 모든 쌍의 합을 계산한 뒤, 해당 값의 제곱근이 정수인지 검사하는 것입니다. 수식으로 표현하면 sqrt(Arr[i]+Arr[j]) − floor(sqrt(Arr[i]+Arr[j])) == 0 을 만족하면 그 합은 완전제곱수입니다.
예제로 이해하기
입력 − Arr[] = { 4, 3, 2, 1, 2, 4 }, N = 6
출력 − 합이 완전제곱수인 쌍의 개수: 2
설명 −
Arr[1]+Arr[3]=4, sqrt(4)-floor(4)=0 → 4는 완전제곱수 Arr[2]+Arr[4]=4, sqrt(4)-floor(4)=0 → 4는 완전제곱수 나머지 쌍들의 합은 7, 6, 5, 8로 모두 완전제곱수가 아닙니다.
입력 − Arr[] = { 3, 3, 3, 3, 3 }, N = 5
출력 − 합이 완전제곱수인 쌍의 개수: 0
설명 − 모든 쌍의 합이 6으로, 6은 완전제곱수가 아니므로 조건을 만족하는 쌍은 없습니다.
알고리즘 접근 방법
- 임의의 양의 정수로 초기화된 크기 N(> 0)의 정수 배열 Arr[]을 준비합니다.
- 배열의 길이를 저장할 변수 n을 선언합니다.
- 함수 countPairs(int arr[], int n)는 배열과 그 길이를 입력받아, 합이 완전제곱수가 되는 쌍의 개수를 반환합니다.
- 두 개의 중첩 for 루프를 사용하여 가능한 모든 쌍을 탐색합니다.
- 외부 루프는 0 ≤ i < n−1 범위에서, 내부 루프는 i < j < n 범위에서 순회합니다.
- 각 반복마다 arr[i] + arr[j]의 합을 계산합니다.
- 합의 제곱근을 sqrt(sum)으로 구합니다.
- sqr − floor(sqr) == 0 인지 확인합니다. 참이라면 합이 완전제곱수이므로 count를 증가시킵니다.
- 모든 루프가 종료되면 count에는 조건을 만족하는 쌍의 총 개수가 저장됩니다.
- count 값을 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
int count=0;
int sum=0;
double sqr=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
sum=arr[i]+arr[j];
sqr=sqrt(sum);
if( sqr-floor(sqr)==0 ){
count++;
//cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //쌍 출력용(필요 시 주석 해제)
}
}
}
return count;
}
int main(){
int arr[] = { 1, 2, 4, 8, 5, 6 };
// 배열의 크기 계산
int n = sizeof(arr) / sizeof(int);
cout <<endl<<"Pairs whose sum is perfect square :"<<countPairs(arr, n);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Pairs whose sum is perfect square :2
이 알고리즘은 두 개의 중첩 루프를 사용하므로 시간 복잡도는 O(N²), 추가 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다. 배열의 크기가 매우 큰 경우에는 해시 맵 등을 활용해 탐색 과정을 최적화하는 방법도 고려할 수 있습니다.