주어진 N개의 선분을 이용해 만들 수 있는 평행사변형의 최대 개수를 구하는 것이 이번 문제의 목표입니다. 단, 각 선분은 하나의 평행사변형에 최대 한 번만 사용할 수 있다는 조건이 붙습니다.
예시를 통해 문제를 좀 더 구체적으로 살펴보겠습니다.
입력 − Arr[] = {8, 3, 1, 3, 8, 7, 1, 3, 5, 3}
출력 − 2
설명 − 주어진 선분들로 만들 수 있는 두 개의 평행사변형은 각각 변의 길이가 8, 1, 8, 1인 평행사변형과 3, 3, 3, 3인 평행사변형입니다.
입력 − Arr[] = {7, 9, 9, 7}
출력 − 1
문제 해결 접근 방법
핵심 아이디어는 간단합니다. 평행사변형은 서로 같은 길이의 변 두 쌍으로 이루어지므로, 네 변이 모두 같은 경우와 길이가 같은 두 쌍의 변으로 만드는 경우를 나누어 계산하면 됩니다.
- 만들 수 있는 평행사변형의 최대 개수는 '네 변이 모두 같은 경우'로 만들 수 있는 평행사변형 수와 '길이가 같은 두 쌍의 변'으로 만들 수 있는 평행사변형 수를 합한 값입니다.
- MaxParr() 함수에서는 빈도 배열의 크기로 사용할 변수를 L = Arr[0]으로 초기화합니다.
- i=1부터 i<N까지 반복하며 Arr[i] > L인지 확인하고, 참이라면 L = Arr[i]로 갱신합니다. 반복문이 끝난 뒤에는 L을 1 증가시킵니다.
- 그다음 빈도 배열 int Freq[L] = {0}을 초기화하고, i=0부터 i<N까지 반복하면서 각 선분의 등장 횟수를 1씩 증가시킵니다.
- 최종 평행사변형 개수를 저장할 int형 변수 count = 0을 초기화합니다.
- i=0부터 i<L까지 반복하면서 네 변이 모두 같은 평행사변형을 만들 수 있는지 확인하고, 가능하다면 그 개수만큼 count를 증가시킵니다.
- 길이가 같은 두 변으로 만들 수 있는 평행사변형의 수를 저장할 int형 변수 left = 0을 초기화합니다.
- 마지막으로 i=0부터 i<L까지 반복하면서 Freq[i] >= 2인지 확인하고, 참이면 left에 1을 더합니다.
- count += left / 2를 수행한 후 count를 반환합니다.
이 알고리즘의 시간 복잡도는 O(N + L)로, 선분의 개수와 최대 선분 길이에 비례해 선형적으로 증가하므로 매우 효율적입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int MaxParr(int N, int Arr[]){
//빈도 배열의 길이 찾기
int L = Arr[0];
for (int i = 1; i < N; i++){
if (Arr[i] > L)
L = Arr[i];
}
L = L + 1;
int Freq[L] = {0};
for (int i = 0; i < N; i++){
//각 선분의 등장 횟수 증가
Freq[Arr[i]] += 1;
}
//평행사변형의 개수를 저장할 변수
int count = 0;
for (int i = 0; i < L; i++){
/*네 변이 모두 같은 평행사변형*/
count += int(Freq[i] / 4);
Freq[i] = Freq[i] % 4;
}
int left = 0;
for (int i = 0; i < L; i++){
//2번 이상 남아 있는 선분 세기
if (Freq[i] >= 2)
left += 1;
}
/*길이가 같은 두 변으로 만들 수 있는 평행사변형을 최종 개수에 합산*/
count += left / 2;
return count;
}
int main(){
int N = 10;
int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3};
cout<< MaxParr(N, Arr);
}
실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻습니다 −
2