n개의 양수로 이루어진 배열이 주어졌을 때, arr[x]와 arr[y]의 곱이 짝수 또는 홀수가 되는 순서쌍 (arr[x], arr[y])의 개수를 세는 것이 목표입니다. 이때 (arr[i], arr[j])와 (arr[j], arr[i])는 서로 다른 쌍으로 각각 계산합니다.
두 개의 for 루프를 사용해 배열을 순회하며 가능한 모든 쌍을 확인합니다. 각 쌍의 곱을 계산한 뒤, 곱이 짝수라면 짝수 곱 쌍 카운트를 2씩 증가시키고, 홀수라면 홀수 곱 쌍 카운트를 2씩 증가시킵니다.
예제를 통해 자세히 살펴보겠습니다.
예제 1
입력 − Arr[]= { 1,1,2,3 }, N=4
출력 − 짝수 곱 쌍의 개수: 6, 홀수 곱 쌍의 개수: 6
설명 − 유효한 홀수 곱 쌍은 다음과 같습니다.
Arr[0] & Arr[1] → (1,1), Arr[1] & Arr[0] → (1,1) → count=2
Arr[0] & Arr[3] → (1,3), Arr[3] & Arr[0] → (3,1) → count=2
Arr[1] & Arr[3] → (1,3), Arr[3] & Arr[1] → (3,1) → count=2
합계 = 6
유효한 짝수 곱 쌍:
Arr[0] & Arr[2] → (1,2), Arr[2] & Arr[0] → (2,1) → count=2
Arr[1] & Arr[2] → (1,2), Arr[2] & Arr[1] → (2,1) → count=2
Arr[2] & Arr[3] → (2,3), Arr[3] & Arr[2] → (3,2) → count=2
합계 = 6
예제 2
입력 − Arr[]= { 2,2,2 }, N=3
출력 − 짝수 곱 쌍의 개수: 6, 홀수 곱 쌍의 개수: 0
설명 − 유효한 짝수 곱 쌍은 다음과 같습니다.
Arr[0] & Arr[1] → (2,2), Arr[1] & Arr[0] → (2,2) → count=2
Arr[1] & Arr[2] → (2,2), Arr[2] & Arr[1] → (2,2) → count=2
Arr[0] & Arr[2] → (2,2), Arr[2] & Arr[0] → (2,2) → count=2
합계 = 6
모든 원소가 짝수이므로 홀수 곱을 갖는 쌍은 존재하지 않습니다.
프로그램에서 사용된 접근 방식
- 임의의 숫자로 초기화된 정수 배열 arr[]를 준비합니다.
- 배열 Arr[]의 길이를 저장하는 변수 n을 선언합니다.
- countPairs(int arr[], int n) 함수는 배열과 그 길이를 입력으로 받아 짝수 곱 및 홀수 곱을 갖는 쌍의 개수를 출력합니다.
- 두 개의 for 루프를 사용해 배열을 순회하며 각 쌍의 원소를 확인합니다.
- 바깥 루프는 0 ≤ i < n-1 범위에서, 안쪽 루프는 i < j < n 범위에서 실행됩니다.
- arr[i]*arr[j]%2==0 인지 검사합니다. 조건이 참이면 (arr[i],arr[j])와 (arr[j],arr[i]) 두 쌍이 모두 해당되므로 짝수 곱 쌍 카운트(count1)를 2씩 증가시킵니다.
- 조건이 거짓이면 홀수 곱 쌍 카운트(count2)를 2씩 증가시킵니다.
- 모든 루프가 종료되면 count1에는 짝수 곱을 갖는 쌍의 총 개수가, count2에는 홀수 곱을 갖는 쌍의 총 개수가 저장됩니다.
- 결과로 count1과 count2를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void countPairs(int arr[], int n){
int count1=0; //짝수 곱 쌍
int count2=0; //홀수 곱 쌍
int prod=1;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
prod=arr[i]*arr[j];
if(prod%2==0) //곱이 짝수인 경우
{ count1+=2; } //(a,b)와 (b,a)를 두 쌍으로 계산
else
{ count2+=2; }
}
}
cout<<"Even Product pairs: "<<count1;
cout<<endl<<"Odd Product pairs: "<<count2;
}
int main(){
int arr[] = { 1,2,7,3 };
int n = sizeof(arr) / sizeof(int);
countPairs(arr, n);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Even Product pairs: 6
Odd Product pairs: 6
참고: 더 효율적인 방법
두 수의 곱이 홀수가 되려면 두 수가 반드시 모두 홀수여야 합니다. 따라서 배열에서 홀수의 개수를 k라고 하면, 홀수 곱 쌍의 개수는 k×(k−1)이고, 전체 순서쌍의 개수 n×(n−1)에서 이 값을 빼면 짝수 곱 쌍의 개수를 구할 수 있습니다. 이 방법을 사용하면 이중 루프 없이 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.