30237번 - 합집합 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 360 | 207 | 195 | 67.708% |
문제
양의 정수로 구성된 집합 $S_{1}, S_{2}, \ldots, S_{n}$이 주어진다. $S_{1}, S_{2}, \ldots, S_{n}$ 중 몇 개를 적당히 골라서, 그 합집합$^{\dagger}$이 $S$와 같아지게 할 수 있다면 $S$를 생성 가능하다고 한다. $0$개를 선택할 수도 있기 때문에, 공집합은 항상 생성 가능하다.
집합 $S$가 생성 가능하고, $S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$일 때, $S$의 원소의 개수의 최댓값을 구하여라.
$^{\dagger}$ 집합 $A_1, A_2, \ldots, A_k$의 합집합은 $A_1, A_2, \ldots, A_k$ 중 하나 이상에 포함된 수의 집합으로 정의하며, $A_1 \cup A_2 \cup \ldots \cup A_k$와 같이 표기한다. 예를 들어, $\{2, 4, 6\} \cup \{2, 3\} \cup \{3, 6, 7\} = \{2, 3, 4, 6, 7\}$이다.
입력
각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 $t$가 주어진다($1 \le t \le 100$). 다음 줄부터 각각의 테스트 케이스가 주어진다.
각각의 테스트 케이스의 첫 번째 줄에 정수 $n$이 주어진다 ($1 \le n \le 50$).
다음 $n$개의 줄에 $S_{1}, S_{2}, \ldots, S_{n}$의 정보가 주어진다. 이 중 $i$번째 줄에는 $S_{i}$의 원소의 개수 $k_{i}$와 $S_{i}$의 원소 $s_{i, 1}, s_{i, 2}, \ldots, s_{i, k_{i}}$가 공백으로 구분되어 주어진다 ($1 \le k_{i} \le 50$, $1 \le s_{i, 1} < s_{i, 2} < \ldots < s_{i, k_{i}} \le 50$).
출력
각각의 테스트 케이스마다 정답을 출력한다.
예제 입력 1
4 3 3 1 2 3 2 4 5 2 3 4 4 4 1 2 3 4 3 2 5 6 3 3 5 6 3 4 5 6 5 1 1 3 3 6 10 1 9 2 1 3 3 5 8 9 1 2 4 28
예제 출력 1
4 5 6 0
노트
첫 번째 테스트 케이스에서, $S = S_{1} \cup S_{3} = \{1, 2, 3, 4\}$일 때 원소 개수가 최대이다.
두 번째 테스트 케이스에서, $S = S_{2} \cup S_{3} \cup S_{4} = \{2, 3, 4, 5, 6\}$일 때 원소 개수가 최대이다.
세 번째 테스트 케이스에서, $S = S_{2} \cup S_{5} = S_{2} \cup S_{3} \cup S_{5} = \{3, 5, 6, 8, 9, 10\}$일 때 원소 개수가 최대이다.
네 번째 테스트 케이스에서, 가능한 $S$는 $S = \varnothing$로 유일하다.
출처
Contest > Codeforces > Codeforces Round 899 (Div. 2) B번
- 문제를 만든 사람: puppy
- 문제를 검수한 사람: koosaga, vector, silverwolf, qwerasdfzxcl, mjhmjh1104, mingyu331, lys9546, lisifu, lighton, leinad2, alex0211, kongum, kep1er07, jk410, jamesoh1201, gs20036, fs_edge, flappybird, chansol, benedict0724
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호