양의 정수로 이루어진 배열 arr[]과 GCD(최대공약수) 값들이 담긴 배열 GCD[]가 주어졌을 때, arr[]의 원소들로 만들 수 있는 부분집합 중에서 GCD[]에 명시된 GCD 값을 갖는 부분집합의 개수를 구하는 것이 목표입니다.
예제 1
입력
arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5}출력
주어진 GCD와 같은 값을 가지는 집합의 부분집합 개수: 1 2 2
설명
GCD가 2인 부분집합은 [10, 6] 입니다. GCD가 3인 부분집합은 [3], [6, 3] 입니다. GCD가 5인 부분집합은 [5], [10, 5] 입니다.
예제 2
입력
arr[] = {10, 21, 7, 8}, GCD[] = {2, 7, 5}출력
주어진 GCD와 같은 값을 가지는 집합의 부분집합 개수: 1 2 0
설명
GCD가 2인 부분집합은 [10, 8] 입니다. GCD가 7인 부분집합은 [7], [21, 7] 입니다. GCD가 5인 부분집합은 존재하지 않습니다.
문제 해결 접근 방식
이 방법에서는 unordered_map<int, int> 타입의 um_1을 사용해 arr[] 원소들의 빈도수를 저장하고, 비슷한 맵 um_2를 사용해 주어진 GCD 값을 갖는 부분집합의 개수를 저장합니다. 먼저 arr[] 원소들 중 최댓값을 count로 설정합니다. 그 다음 i = count부터 i >= 1까지 반복하면서 현재 GCD 값에 대한 부분집합의 개수를 계산합니다.
핵심 아이디어는 다음과 같습니다. um_1에서 i의 배수인 원소들의 개수를 세는데, 이 개수를 total이라 하면 GCD가 정확히 i인 부분집합의 개수는 2total − 1 − temp가 됩니다. 여기서 temp는 GCD가 i보다 큰 배수들에 해당하는 부분집합의 개수를 의미합니다.
알고리즘 단계
arr[]과GCD[], 두 개의 배열을 준비합니다.subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD)함수는 두 배열과 각각의 길이를 인자로 받아, 주어진 GCD 값과 일치하는 부분집합의 개수를 반환합니다.초기
count를 0으로 설정합니다.for 루프를 통해
arr[]을 순회하면서count를 최댓값으로 갱신하고,um_1[arr[i]]++연산으로 각 원소의 빈도수를 기록합니다.i = count부터i >= 1까지 for 루프를 돌며,total은i자체의 빈도수로 초기화하고temp는 0으로 초기화합니다.내부 루프에서
j = 2부터j * i <= count까지 순회하며um_1[j * i]를total에 더하고,um_2[j * i]를temp에 더합니다.두 루프가 모두 끝나면
um_2[i] = (1 << total) − 1 − temp로 값을 설정합니다.마지막으로
um_2[GCD[i]]를 출력하여 주어진 GCD 값에 해당하는 부분집합의 개수를 확인합니다.
구현 예제
#include<bits/stdc++.h>
using namespace std;
void subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD){
unordered_map<int, int> um_1, um_2;
int count = 0;
for (int i=0; i<size_arr; i++){
count = max(count, arr[i]);
um_1[arr[i]]++;
}
for (int i = count; i >=1; i--){
int temp = 0;
int total = um_1[i];
for (int j = 2; j*i <= count; j++){
total += um_1[j*i];
temp += um_2[j*i];
}
um_2[i] = (1<<total) - 1 - temp;
}
cout<<"주어진 GCD와 같은 값을 가지는 집합의 부분집합 개수: ";
for (int i=0; i<size_GCD ; i++){
cout<<um_2[GCD[i]]<<" ";
}
}
int main(){
int GCD[] = {2, 3};
int arr[] = {9, 6, 2};
int size_arr = sizeof(arr)/sizeof(arr[0]);
int size_GCD = sizeof(GCD)/sizeof(GCD[0]);
subset_GCD(arr, size_arr, GCD, size_GCD);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
주어진 GCD와 같은 값을 가지는 집합의 부분집합 개수: 2 1