21398번 - 동생에게 져주기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 49 | 22 | 17 | 58.621% |
문제
Alice 와 Albert 는 종종 카드 게임을 하는데, 동생인 Albert는 게임에서 지면 너무 슬퍼하기 때문에 Alice는 일부러 져주려고 한다.
두 사람이 하는 게임은 n장의 카드를 이용하는데 각 카드에는 영문 대문자 (A-Z) 하나가 적혀있다. 아래와 같은 규칙으로 게임을 하는데, 동생인 Albert는 아직 어리기 때문에 항상 Alice가 예측한대로 플레이 한다.
- 먼저, 두 사람이 알파벳이 적힌 카드 n장을 좌측부터 우측으로 임의의 순서로 나열한다.
- 두 사람이 번갈아가며 카드를 한 장씩 가져오는데, 가장 좌측 혹은 가장 우측에 놓인 카드만 가져올 수 있다.
- Albert가 먼저 시작하고, 그 후 번갈아가면서 카드를 가져온다.
- Albert의 차례에는 "ALBERT" 를 구성하는 6개의 알파벳 중 하나가 적힌 카드를 가져오면 Albert가 2점을 얻는다.
- Alice의 차례에는 "ALICE"를 구성하는 5개의 알파벳 중 하나가 적힌 카드를 가져오면 Alice가 1점을 얻는다.
- Albert는 항상 아래 규칙에 따라 카드를 가져온다:
- 만약 가장 좌측과 가장 우측에 놓인 카드가 모두 2점을 주는 카드라면 왼쪽에 놓인 카드를 가져온다.
- 만약 가장 좌측과 가장 우측에 놓인 카드가 점수를 주는 카드가 아니라면 우측에 놓인 카드를 가져온다.
- 만약 두 카드 중 한 장만 2점을 주는 카드라면, 해당 카드를 가져온다.
Alice는 Albert에게 일부러 져주되 게임이 끝났을 때 (Albert의 점수 - Alice 의 점수)가 최소가 되도록 하고 싶다.
예를 들어, n = 4이고 바닥에 놓인 카드가 "BCCB" 라 하자.
- 1턴: Albert는 위 규칙에 따라 가장 좌측에 놓인 카드 "B"를 가져와 2점을 얻는다. 남은 카드는 "CCB" 이다.
- 2턴: Alice는 가장 좌측의 "C"를 가져오거나 가장 우측의 "B"를 가져올 수 있다.
- 가장 좌측의 C를 가져온 경우: 1점을 얻고, "CB"가 남는다. Albert는 가장 우측의 B를 가져오고, Alice가 마지막 남은 C를 가져와 두 사람의 점수는 4점 (Albert) 2점 (Alice)가 되어 점수의 차이가 2가 된다.
- 가장 우측의 B를 가져온 경우: 0점을 얻고, "CC"가 남는다. Albert는 가장 우측의 C를 가져오고, Alice가 마지막 남은 C를 가져와 두 사람의 점수는 2점 (Albert) 1점 (Alice)가 되어 점수의 차이가 1이 된다.
- 이 예제의 경우, Alice가 최선을 다해 Albert가 이기되 점수 차이를 최소화 한다면 1점 차로 아슬아슬하게 질 수 있다.
다른 예로, n = 4이고 바닥에 놓인 카드가 "CLCD"라 하자.
- 1턴: Albert는 위 규칙에 따라 가장 우측에 놓인 카드 "D"를 가져와 0점을 얻는다. 남은 카드는 "CLC" 이다.
- 2턴: Alice는 좌측 혹은 우측의 C를 가져올 수 있다.
- 가장 좌측의 C를 가져온 경우: 1점을 얻고 "LC"가 남는다. Albert는 규칙대로 좌측의 L을 가져오고 (2점), Alice가 마지막 남은 C를 가져와 동점으로 게임이 끝난다.
- 가장 우측의 C를 가져온 경우: 1점을 얻고 "CL"이 남는다. Albert는 규칙대로 우측의 L을 가져오고 (2점), Alice가 마지막 남은 C를 가져와 동점으로 게임이 끝난다.
- 이 예제의 경우, 만약 Albert가 처음에 가장 좌측에 놓인 C를 가져온다면, Alice가 그 다음 턴에 우측에 놓인 D를 가져오고, Albert가 L을 가져와 2점을 얻고 Alice가 마지막 남은 C를 가져와서 1점차로 아슬아슬하게 져줄 수 있지만, Albert는 점수를 얻지 못하는 상황에서는 항상 우측의 카드를 가져오기 때문에 Alice가 져줄 방법이 없다.
입력으로 좌측에서 우측으로 나열된 n장의 카드에 적힌 알파벳이 주어졌을 때, Alice가 최소한의 점수차로 져줄 수 있는 방법을 찾아보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 한 줄에 걸쳐 영문 대문자로만 구성된 문자열이 공백없이 주어진다.
출력
각 테스트 케이스에 대해 Alice가 최소의 점수차로 Albert에게 져줄 때 이 점수 차이가 무엇인지 출력한다.
만약 져줄 수 있는 방법이 없을 경우 -1을 출력한다.
제한
- 1 ≤ T ≤ 30
- 1 ≤ n ≤ 150 (n: 문자열의 길이)
- 입력으로 주어지는 문자열은 영문 대문자 (A-Z)로만 구성되어있다.
예제 입력 1
5 ABA BBB BCCB CLCD ALBERT
예제 출력 1
3 4 1 -1 4
예제 1: Albert가 가장 좌측의 A를 가져오고 (+2점), Alice는 가장 우측의 A를 가져온 후 (+1점), Albert 가 마지막 카드인 B를 가져와 (+2점) 점수 차이는 3이 된다. 2점 이하로 져주는 방법은 없다.
예제 2: Alice가 득점할 수 있는 방법은 없고, Albert가 4점을 얻어 점수차이가 4가 된다.
예제 3-4: 본문에서 다루었다.
예제 5: 두 사람이 순서대로 처음 4턴 동안 A, L, B, E를 가져와서 Albert가 4점, Alice가 2점을 얻은 후 남은 카드는 "RT"가 된다. Albert는 R을 가져오고 (총 6점) Alice가 T를 가져와 점수 차이는 4점이 된다.
시간 제한
- Java 8: 1.5 초
- PyPy3: 6.5 초
- Java 8 (OpenJDK): 1.5 초
- Java 11: 1.5 초
- Kotlin (JVM): 1.5 초
- Java 15: 1.5 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호