19241번 - 해적과 보석 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 256 MB | 206 | 73 | 57 | 38.255% |
문제
Alice 와 Bob 두 해적은 최근 보물섬에서 엄청난 양의 보물을 발견했다. 총 N개의 보물 상자를 발견했는데, 공평하게 번갈아가며 보물 상자를 하나씩 골라 가지기로 하였다. 각 보물 상자의 가치는 객관적으로 정하기 어렵기 때문에 두 사람 모두 자신이 생각하는 가치가 얼마인지 적어서 서로에게 공유했다. 즉, i번째 보물 상자는 Alice에겐 A[i] 달러 만큼의 가치를 갖고 Bob에겐 B[i] 달러 만큼의 가치를 갖는다. 상자를 나누어 갖기 위해 Alice부터 시작하여 Alice와 Bob은 번갈아가며 남은 상자들 중 하나를 가져가기로 했다. 상자를 하나 가져오면 상대방의 차례가 되며, N개의 상자가 모두 주인을 찾은 후 둘은 각자 갈 길을 떠나기로 했다.
편의상 보물 상자를 모두 나눈 후 Alice가 가져간 상자의 (Alice 기준대로의) 가치의 총합을 ScoreA라 하고 Bob이 가져간 상자의 (Bob 기준대로의) 가치의 총합을 ScoreB라 하자. Alice와 Bob은 서로 약속은 지키는 의리있는 해적이지만, 욕심이 많기 때문에 Alice의 목표는 (ScoreA - ScoreB)가 최대가 되도록 상자를 선택하는 것이고 Bob의 목표는 (ScoreB - ScoreA)가 최대가 되도록 상자를 선택하는 것이다.
이 두 사람은 언제나 최선을 다해서 어떤 상자를 가져갈지 결정한다.
예를 들어 N = 3 인 경우 세 개의 보물 상자가 있으며, 각 해적이 생각하는 보물 상자의 가치는 아래와 같다.
- 상자1: A[1] = 10, B[1] = 5
- 상자2: A[2] = 100, B[2] = 90
- 상자 3: A[3] = 2, B[3] = 0
이 때 Alice가 상자 2를 먼저 가져가고, 그 후 Bob이 상자 1을 가져간 후, 마지막으로 Alice가 상자 3을 가져간다면, Alice는 총 102 달러 만큼 보물을 챙기고 Bob은 총 5달러 만큼 보물을 챙기게 된다. 만약 Alice가 자신의 첫 차례에 상자 2가 아닌 다른 상자를 가져간다면 (상자 1 혹은 상자 3), Bob은 자신의 차례에 상자 2를 가져갈테니, 이 경우 Alice는 10+2 = 12 달러 그리고 Bob은 90달러 만큼의 보물을 챙기게 된다. 따라서 Alice가 최선을 다한다면 첫 차례에 반드시 보물 2를 가져가야 한다.
보물 상자의 수 N과 해적 둘이 각자 생각하는 보물 상자의 가치가 주어졌을 때, 두 사람이 최선을 다해 각자의 목표를 최대화 했을 때 (ScoreA - ScoreB) 값이 무엇인지 구하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스에 대해 첫 줄에 정수 N이 주어지며 이는 보물 상자의 수를 나타낸다.
다음 N줄에 걸쳐서 각 보물의 가치가 공백으로 구분되어 주어진다 (첫 수는 Alice가 생각하는 가치, 두 번째 수는 Bob이 생각하는 가치).
출력
각 테스트 케이스에 대하여 두 사람이 최선을 다해 게임을 플레이 했을 때, (ScoreA - ScoreB) 값을 구하여 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100,000
- 0 ≤ A[i], B[i] ≤ 100,000
예제 입력 1
5 3 10 5 100 90 2 0 3 90 100 5 10 0 2 3 10 100 100 10 50 60 4 20 10 15 20 5 8 8 9 3 0 100 0 1000 0 10
예제 출력 1
97 80 50 5 -100
테스트 케이스 1
문제에서 다루었다.
테스트 케이스 2
예제 1에서 쓰인 세 개의 보물 상자와 같지만 두 사람이 생각하는 가치가 바뀌었다. 이 경우 Alice는 상자 1을 먼저 가져가서 90 달러를 획득하고, Bob은 상자 2를 가져가서 10달러를 획득한다. 마지막으로, Alice는 남겨진 상자 3을 가져가서 0달러를 획득하여 (ScoreA-ScoreB)는 80이 된다.
테스트 케이스 3
이 경우, Alice 와 Bob 모두 어떤 상자를 가져가더라도 항상 같은 결과가 나온다.
테스트 케이스 4
Alice는 첫 차례에 상자 2를 가져가 15달러를 획득하고 (이 방법이 Alice에게는 최선의 방법이기에 반드시 이 상자를 가져와야 한다), Bob은 자신의 첫 차례에 상자 1을 가져가 10달러를 획득하고 (마찬가지로, Alice가 이미 상자 2를 가져간 이후에 상자 1을 고르는 것이 Bob에게는 최선이다).
Alice의 두 번째 차례에 상자 4를 가져가 8 달러를 획득한 후, 마지막으로 Bob이 상자 3을 가져가 8달러를 획득한다. ScoreA = 15+8=23, ScoreB = 10 + 8 = 18 이 되어 ScoreA-ScoreB = 5가 된다.
테스트 케이스 5
Alice는 선택에 관계없이 0달러를얻게 된다. 다만, 첫 차례에 상자 2를 가져올 경우, Bob은 다음 차례에 상자 1을 가져올 수 밖에 없고, 따라서 ScoreA - ScoreB = -100 으로 (비록 음수이긴 하지만) Alice에게는 이것이 최선의 결과가 된다.
시간 제한
- Java 8: 3 초
- Python 3: 2.5 초
- PyPy3: 2.5 초
- Java 8 (OpenJDK): 3 초
- Java 11: 3 초
- Python 2: 2.5 초
- PyPy2: 2.5 초
- Kotlin (JVM): 3 초
- Java 15: 3 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호