모든 집합의 합집합과 다르게 되는 일부를 골라 만든 최대 합집합

30237번: 합집합 (acmicpc.net)

 

s1,s2,...,sn 집합이 주어질때, 이들 중 일부를 골라 만든 합집합 s와 모든 집합의 합집합 s1 ∪ s2 ∪ ... ∪ sn이

 

서로 다르게 되는 가장 큰 합집합 s를 구하고 싶다

 

집합을 기준으로 s1 넣어보고 s2는 넣지말고... sn은 넣고 등등으로 해서 s를 다 조사해보는건 $O(2^{50})$으로 어렵다

 

모든 집합의 합집합을 먼저 구하고 그 중에서 하나의 집합만 빼는 방법은 어떨까?

 

집합 합칠수록 원소가 많아질테니까...

 

s2 ∪ s3 ∪ ... ∪ sn

 

s1 ∪ s3 ∪  ... ∪  sn

 

...

 

이러면 O(N)정도니까 괜찮을것 같은데

 

[1], [3,6,10], [9], [1,3], [5,8,9]를 보면

 

모든 집합의 합집합은 [1,3,5,6,8,9,10]

 

집합 하나만 빼서 해본다면

 

[1,3,5,6,8,9,10]

 

[1,3,5,8,9]

 

[1,3,5,6,8,9,10]

 

[1,3,5,6,8,9,10]

 

[1,3,6,9,10]

 

으로 5개가 최대인데

 

사실 [3,6,10]과 [5,8,9]의 합집합으로 [3,5,6,8,9,10]으로 6개가 최대이게 만들 수 있다

 

--------------------------------------------------------------------------------------------------------------------------------------------

 

그렇다면 모든 집합의 합집합 [1,3,5,6,8,9,10]에서 각각의 원소가 들어가지 않은 집합들의 합집합을 비교하는건 어떨까?

 

s1,s2,...,sn중 1이 들어가지 않은 집합을 모두 고른 다음 합집합을 구해보고

 

3이 들어가지 않은 집합을 모두 골라 합집합을 구해보고

 

5가 들어가지 않은 집합을 모두 골라 합집합을 구해보고...

 

...

 

10이 들어가지 않은 집합을 모두 골라 합집합을 구해본다면?

 

모든 집합의 합집합의 원소의 개수는 많아야 2500개라 충분히 할만하다

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):

    n = int(stdin.readline())

    S = []

    for _ in range(n):
        
        A = list(map(int,stdin.readline().split()))

        k = A[0]
        A = A[1:]
        S.append(set(A))
    
    #모든 집합들의 합집합 X
    X = set()

    for s in S:
        
        for i in s:
            
            X.add(i)

    answer = 0
    
    #X의 한 원소 x에 대하여
    for x in X:
        
        #s1,s2,..,sn중 x가 들어가지 않은 집합을 고르고 
        A = []

        for s in S:
            
            if x not in s:
                
                A.append(s)
        
        #x가 들어가지 않은 집합의 합집합을 구한 다음
        B = set()

        for a in A:
            
            for i in a:
                
                B.add(i)
        
        #x가 들어가지 않은 집합의 합집합들 중 최대 크기를 찾는다
        if answer < len(B):
            
            answer = len(B)

    print(answer)