18771번 - 오픈소스 버그 잡기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 256 MB | 55 | 26 | 22 | 51.163% |
문제
당신은 취미로 오픈 소스 SDK인 "Le Great SDK" (LG SDK)의 버그를 종종 고치곤 한다. 최근 발견된 다양한 버그들과 그들의 연관성 때문에 재미있는 문제를 풀게 되었다.
현재 총 n개의 버그가 신고된 상태이고, 각 버그 리포트를 읽어본 후 각 버그를 고치는 것이 얼마나 재미있을지 수치화 했다. 버그는 1번부터 n번까지 번호가 매겨져 있다.
구체적으로 i번 버그를 고친다면 당신은 fi 만큼의 재미를 얻게 되는데, 이 값은 양의 정수 혹은 음의 정수이다. 이 값이 음의 정수인 경우는 너무 지루한 버그라서 버그를 고치는 과정을 즐기지 못하는 의미이다.
흥미도가 양수인 버그만 고칠 수 있다면 좋겠지만, 버그 리포트를 읽어본 결과 어떤 버그는 해당 버그를 고치기 위해 다른 버그까지 고쳐야 하는 관계가 있음을 알게 되었다. 즉, 버그 i를 고치기 위해서는 원치 않더라도 다른 버그 j를 고쳐야만 버그 i를 온전히 고쳤다고 할 수 있는 경우가 있다.
예를 들어, 현재까지 신고된 버그가 총 n = 3개이고 흥미도는 f1 = 5, f2 = -2, f3 = 3 이라고 하자. 버그 1을 고치기 위해서는 버그 2도 함께 고쳐야 하고, 버그 2를 고치기 위해서 다른 버그를 고칠 필요는 없다. 마지막으로 버그 3을 고치기 위해서는 버그 1,2를 모두 고쳐야 한다.
이 경우, 버그 2만 고친다면 총 흥미도는 -2가 될 것이고, 버그 1, 2를 고친다면 흥미도가 3이 되어 양수가 된다. 버그 셋을 모두 고친다면 총 흥미도가 6이 된다.
버그의 수와 각 버그의 흥미도, 그리고 버그 간의 관계가 주어졌을 때, 흥미도가 최대화 되도록 하는 버그만 고치고 싶다. 이 경우 달성할 수 있는 흥미도의 최댓값을 구해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫째 줄에 버그의 수 n이 주어진다. 둘째 줄에는 n개의 정수가 공백으로 구분되어 주어지는데 이는 각 버그의 흥미도 fi를 의미한다.
다음 n줄에 걸쳐서 각 줄에 하나 이상의 정수가 주어진다. i번째 줄에 주어진 첫 정수는 i번째 버그를 고치기 위해 몇 개의 다른 버그를 고쳐야 하는지 나타낸다. 만약 그 수가 xi 라면 같은 줄에 공백으로 구분된 xi개의 정수가 더 주어지며 이들이 버그 i를 고치기 위해 함께 고쳐야 다른 버그들을 나타낸다. 이때 주어지는 xi개의 버그는 중복으로 주어지지 않는다.
출력
각 테스트 케이스 마다 흥미도의 최댓값을 한 줄에 하나씩 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 500
- 1 ≤ |fi| ≤ 1,000,000
- 0 ≤ xi ≤ min(300, n-1)
서브태스크 1 (6점)
- 1 ≤ n ≤ 150
서브태스크 2 (21점)
- 1 ≤ n ≤ 500
예제 입력 1
8 4 2 -3 6 -4 1 2 0 2 2 4 1 2 3 2 -6 3 0 0 2 1 2 3 5 -2 3 1 2 0 2 1 2 3 -2 -3 -4 0 0 0 3 1 -1 2 1 2 1 3 1 1 6 -51 -89 -58 21 -6 35 0 4 1 4 3 5 2 4 6 1 1 4 1 4 6 3 1 1 5 -10 -10 -10 -10 39 0 0 0 0 4 1 2 3 4 7 72 96 -45 -69 -46 65 -70 0 1 1 2 1 2 3 1 2 3 2 1 2 4 1 2 3 5 2 3 5
예제 출력 1
1 2 6 0 2 5 0 168
- 테스트 케이스 1: 모든 버그를 다 고치면 총 흥미도가 1이 된다. 버그 1만 고칠 수는 없기에 1, 2를 같이 고치면 흥미도가 -1이 된다. 버그 3을 고치기 위해서는 버그 2, 4도 함께 고쳐야하고 (이 경우 흥미도가 -1), 버그 1도 같이 고치면 총 흥미도가 1이 되어 최대가 된다.
- 테스트 케이스 2: 모든 버그를 다 고치면 흥미도가 -1로 음수가 된다. 버그 1만 고친다면 흥미도 2를 달성할 수 있다. 버그 3을 고치려면 버그 1, 2도 모두 고쳐야 하는데 이 경우 총 흥미도가 -1이므로 최대가 아니다.
- 테스트 케이스 3: 문제에서 다룬 예시이다.
- 테스트 케이스 4: 모든 버그의 흥미도가 음수이므로, 아무 버그도 고치지 않고 흥미도를 0으로 유지하는 것이 최댓값이다.
- 테스트 케이스 5: 버그 1을 고치기 위해서는 버그 2를 고쳐야 하고, 그러기 위해 버그 3을 고쳐야 하는데 버그 3을 고치려면 버그 1을 고쳐야 한다. 이런식으로 엮인 버그들이 있을 수 있으며, 이 경우 세 개의 버그를 모두 고치는 수 밖에 없다. 다행히 세 버그를 모두 고치면 흥미도의 총 합이 2가 되어 최댓값이다.
- 테스트 케이스 6: 버그 1, 버그 4, 그리고 버그 6을 함께 고칠 경우 흥미도의 총 합은 (-51) + 21 + 35 = 5이다. 이 예제에서 버그 4 또는 버그 6을 고치기 위해서는 버그 1을 반드시 고쳐야 한다.
- 테스트 케이스 7: 이 경우 버그 5만 흥미도가 양수인데 다른 모든 버그도 같이 고쳐야한다. 그럴 경우 흥미도의 총 합은 음수가 되고, 아무 버그도 고치지 않는 것이 흥미도의 최댓값이다.
- 테스트 케이스 8: 버그 1, 2를 고치면 총 168의 흥미도를 얻는다. 이 방법이 최댓값이다.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호