시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (하단 참고) | 256 MB | 58 | 14 | 10 | 41.667% |
곧 사내 모의 보안 해커톤 대회가 열릴 예정이며 참가하는 N명의 임직원들은 공격팀 (해킹 담당)과 방어팀 (보안 담당)으로 나뉘게 된다. 모든 임직원이 이전에 참여했던 사내 해킹 연습 대회를 통해 각 임직원의 공격력과 방어력은 수치화 되어 데이터베이스에 저장되어있다. 편의상 i번째 임직원의 공격력은 A[i] 방어력은 B[i]라 하자.
총 N명의 임직원을 공격팀과 방어팀으로 나누는 방법은 2N 가지 존재하지만, 이 중 가장 "적합한" 방법으로 팀을 나누려고 한다. 적합성은 수치화 될 수 있는데, 우선 공격팀에 배장된 모든 임직원들의 공격력 총합과 방어팀에 배정된 (나머지) 모든 임직원들의 방어력 총합을 더한 후, 후술될 "감점"을 적용하여 적합도를 점수화 한다. 팀 배정의 감점 요인은 다음과 같다.
현재 사내에는 M개의 태스크 포스가 있으며 각 태스트 포스에는 2명 이상 N명 이하의 임직원이 속해있다. 만약 같은 태스크 포스에 속한 두 임직원이 서로 다른 팀에 배정된다면, 해당 태스크 포스의 "감점도"에 따라 팀 배정의 적합도 점수가 감점된다. 이 감점은 태스크 포스에 속한 모든 임직원 쌍에 대해 각각 적용한다 (예제 참고).
예를 들어 N = 3 이고 각 임직원의 공격력 / 방어력이 아래와 같다고 해보자.
아울러 태스크 포스가 하나 있고 임직원 1, 임직원 2 두 사람이 속해있으며, 이 태스크 포스의 감점도는 100이라 하자. 만약 공격팀 = {임직원 1, 임직원 2} 그리고 방어팀 = {임직원 3} 으로 배정할 경우, 공격력 총 합은 10+10 = 20, 방어력 총합 = 5, 감점 = 0점이 되어 적합도는 총 25가 된다. 만약 공격팀 = {임직원 1} 그리고 방어팀 = {임직원 2, 임직원 3} 으로 배정할 경우, 공격력 총 합은 10, 방어력 총합 = 5+5 = 10, 감점 = 100점이 되어 적합도는 총 -80이 된다. 만약 공격팀 = {임직원 1, 임직원 2, 임직원 3} 그리고 방어팀 = {} 으로 배정할 경우, 공격력 총 합은 10+10+5 = 25, 방어력 총합 = 0, 감점 = 0점이 되어 적합도는 총 25가 된다. 이 예제의 경우 최대 팀 배정 적합도는 25이며, 상기한 두 가지 방법으로 배정할 수 있다. 예제에서 보여지듯 모든 임직원을 공격팀에 배정하거나 모든 임직원을 방어팀에 배정하는 것도 가능하다. N명의 임직원 이외에도 사내 보안팀이 적절히 공격팀과 방어팀에 나뉘어 배정될 예정이기 때문에 아무 문제 없다.
입력으로 임직원의 수 N, 태스크 포스의 수 M, 각 임직원의 공격력/방어력, 그리고 각 태스크 포스에 속한 임직원의 정보 및 태스크 포스별 감점이 주어졌을 때, 팀 배정 적합도를 최대로 만들 경우의 적합도를 구하고, 그러한 적합도를 가능케하는 공격팀 배정을 출력하는 프로그램을 작성하시오.
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄은 N과 M이 공백으로 구분되어 주어진다.
다음 N줄에 걸쳐 각 줄에 임직원의 공격력과 방어력이 공백으로 구분되어 주어진다.
다음 2M줄에 걸쳐 M개의 태스크 포스에 대한 정보가 (각각 두 줄에 걸쳐) 주어진다.
i번째 태스크 포스에 대한 입력은 두 줄에 나누어서 주어지며, 첫 줄은 태스크 포스에 속한 임직원의 수 (Ki)와 해당 태스크 포스에 속한 임의의 임직원 한 쌍이 다른 팀에 배정 되었을 경우 감점이 되는 정도가 (Si) 주어진다.
두 번째 줄에 태스크 포스에 속한 임직원 번호가 (즉, Ki 개의 정수) 공백으로 구분되어 주어진다. 이 때 주어지는 Ki 개의 정수는 모두 다르다 (즉 각각의 태스크 포스 i의 입력에 주어지는 임직원 번호가 중복인 경우는 없다).
각 테스트 케이스에 대해 두 줄씩 출력한다.
첫 줄에 최대 달성 가능한 팀 배정 적합도를 출력한다.
다음 줄에 공격팀을 출력하는데, 첫 수는 공격팀을 구성하는 임직원의 수이며 같은 줄에 이어서 임직원 번호를 공백으로 구분하여 출력한다.
최대 적합도를 달성한 방법이 여럿인 경우 그 중 아무 방법이라 출력하여도 된다.
임직원 번호는 임의의 순서로 출력해도 무방하다.
4 3 1 10 0 10 0 5 5 2 100 1 2 4 2 10 0 20 10 5 10 1 5 2 2 1 2 3 1 2 3 4 4 2 100 0 200 10 50 10 10 5 2 2 1 2 3 1 2 3 4 4 1 100 0 4 8 2 15 3 51 4 3 1 2 3 4
25 2 1 2 43 2 1 2 360 4 1 2 3 4 165 1 1
테스트 케이스 1: 문제에서 다룬 예시이다. 상기된대로 "3 1 2 3"도 팀 배정도 25를 만족하기 때문에 이 역시 정답으로 간주한다.
테스트 케이스 2
공격팀 = {임직원 1, 임직원 2} / 방어팀 = {임직원 3, 임직원 4}로 배정할 경우 공격력과 방어력 총 합은 (10+20) + (10 + 5) = 45가 된다.
태스크 포스 1의 경우 감점도는 2점이며 임직원 1과 임직원 2가 속해있다. 이 둘은 공격팀에 함께 배정 되었으므로 감점은 없다.
태스크 포스 2의 경우 감점도는 1이며 임직원 2, 임직원 3, 임직원 4 세 사람이 속해있다. 임직원 2와 임직원 3이 다른 팀에 배정되었고 임직원 2와 임직원 4가 다른 팀에 배정되었으므로 각 1점씩 감점하여 팀배정의 총 적합도는 45 - 2 = 43이 된다. (임직원 3과 임직원 4는 같은 팀에 배정 되었으므로 감점하지 않는다.)
테스트 케이스 3
이 경우 모든 임직원을 공격팀에 배정하여 최대 적합도인 360을 달성할 수 있다.
테스트 케이스 4
공격팀 = {임직원 1} / 방어팀 = {임직원 2, 임직원 3, 임직원 4}로 배정할 경우 공격력과 방어력 총합은 100 + (8+15+51) = 174가 된다.
태스크 포스에는 모든 임직원이 속해있으며 감점도는 3점이다. 임직원 1만 다른 팀에 배정 되었으므로 총 세 쌍에 대하여 (임직원 1 - 임직원 2, 임직원 1 - 임직원 3, 임직원 1 - 임직원 4) 감점을 적용하여 174 - 3*3 = 165점이 최종 적합도가 되며, 이 경우가 최적이다.