보석 장식 도안
골드 IV의견: 0
보석 공방 주인 리아는 \(M\)가지 종류의 보석을 모두 전시하고 싶다. 공방에는 \(N\)개의 장식 도안이 있으며, \(i\)번 도안은 특정 보석 종류들을 포함하고 제작비가 \(c_i\)코인이다. 같은 보석 종류는 여러 도안에 걸쳐 중복으로 사용해도 상관없다.
\(M\)가지 보석을 모두 포함하도록 도안을 골랐을 때의 최소 총 제작비를 구하여라. 단, 모든 보석 종류를 포함하는 것이 불가능한 경우에는 \(-1\)을 출력한다.
- \(1 \le M \le 18\)
- \(1 \le N \le 40\)
- \(1 \le c_i \le 10^6\)
- \(1 \le k_i \le M\)
첫째 줄에 보석의 종류 수 \(M\)과 도안 수 \(N\)이 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄 중 \(i\)번째 줄에 \(i\)번 도안의 제작비 \(c_i\), 포함 보석 종류 수 \(k_i\), 그리고 그 보석 종류들의 번호 \(k_i\)개가 공백으로 구분되어 주어진다. 보석 종류 번호는 \(1\) 이상 \(M\) 이하이다.
\(M\)가지 보석을 모두 포함하는 최소 총 제작비를 출력한다. 불가능하면 \(-1\)을 출력한다.
3 3
3 2 1 2
4 2 2 3
5 2 1 3
7
보석 \(1, 2\)를 덮는 도안 \(A\)(비용 \(3\))와 보석 \(2, 3\)을 덮는 도안 \(B\)(비용 \(4\))를 선택하면 세 종류 보석을 모두 덮고 총 비용은 \(7\)이다.
4 5
10 1 1
10 1 2
10 1 3
10 1 4
6 4 1 2 3 4
6
다섯 번째 도안 하나가 네 종류 보석을 모두 덮으므로 비용 \(6\)으로 해결할 수 있다.
riseoj 작성
출처 Original
평가 및 의견
보석 장식 도안
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
보석 장식 도안