마법진 유사도
골드 I의견: 0
마법사 학교에는 \(N\)개의 마법진이 있다. 마법진 \(i\)는 총 \(M\)가지 중 일부 룬 종류의 부분집합을 가진다.
두 마법진 \(i\), \(j\) (\(i < j\))의 유사도는 두 마법진이 공통으로 가진 룬 종류의 수이다.
유사도가 \(K\) 이상인 쌍 \((i, j)\)의 수를 구하여라.
- \(2 \le N \le 500\)
- \(1 \le M \le 500\)
- \(0 \le K \le M\)
- \(0 \le s_i \le M\)
첫째 줄에 마법진 수 \(N\), 룬 종류 수 \(M\), 기준 유사도 \(K\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 각 마법진의 정보가 주어진다. 각 줄의 첫 번째 수는 그 마법진이 가진 룬 종류 수 \(s_i\)이고, 이어서 \(s_i\)개의 룬 번호 (\(1\) 이상 \(M\) 이하의 서로 다른 정수)가 주어진다.
유사도가 \(K\) 이상인 쌍의 수를 출력한다.
4 6 2
3 1 2 3
3 2 3 5
3 1 4 6
3 2 3 4
3
쌍 \((1,2)\): \(\{2,3\}\) 공유 → \(2 \ge 2\) ✓. 쌍 \((1,4)\): \(\{2,3\}\) 공유 → \(2 \ge 2\) ✓. 쌍 \((2,4)\): \(\{2,3\}\) 공유 → \(2 \ge 2\) ✓. 나머지 쌍은 공유 룬이 \(2\) 미만이어서 답은 \(3\).
3 5 2
2 1 2
2 3 4
2 1 5
0
어떤 두 원 쌍도 공유 룬이 \(1\)개 이하여서 답은 \(0\).
riseoj 작성
출처 Original
평가 및 의견
마법진 유사도
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법진 유사도