보안 구역 커버하기
골드 II의견: 0
보안 회사 RISE 는 \(N\) 개의 핵심 자산을 보호해야 합니다. 자산에는 \(1\) 번부터 \(N\) 번까지 번호가 붙어 있습니다.
회사가 운용할 수 있는 순찰 패키지는 \(M\) 종류이며, 각 패키지는 정해진 자산들의 부분집합을 한꺼번에 보호합니다.
모든 자산을 빠짐없이 보호하기 위해 선택해야 하는 순찰 패키지의 최소 개수를 구하세요. 어떻게 선택해도 모든 자산을 보호할 수 없다면 \(-1\) 을 출력합니다.
같은 자산이 여러 패키지에 중복으로 포함되어도 무방합니다.
\(1 \le N \le 20\), \(1 \le M \le 100\)
첫 줄에 자산 수 \(N\) 과 패키지 수 \(M\) 이 주어집니다. (\(1 \le N \le 20\), \(1 \le M \le 100\))
이후 \(M\) 개의 줄에 각 패키지가 보호하는 자산이 주어집니다. 각 줄은 보호 자산 개수 \(k\) 와 \(k\) 개의 자산 번호로 이루어집니다. (\(1 \le k \le N\))
모든 자산을 보호하는 데 필요한 최소 패키지 수, 불가능하면 \(-1\) 을 한 줄에 출력합니다.
4 3
2 1 2
2 2 3
2 3 4
2원소 {1,2}, {2,3}, {3,4} 를 모두 고르면 1~4 전체를 덮으므로 최소 부분집합 수는 3입니다.
3 2
1 1
1 2
-1어떤 집합도 원소 3을 포함하지 않아 전체를 덮을 수 없으므로 -1 을 출력합니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
보안 구역 커버하기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
보안 구역 커버하기