24435번 - 카드 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 77 | 42 | 32 | 53.333% |
문제
Alice와 Bob은 각자 n장의 카드를 갖고 있는데 각 카드에는 $1$보다 크거나 같고, $9$보다 작거나 같은 숫자가 하나씩 적혀 있다. 두 사람은 각자 자신이 가진 카드를 이용해서 최대 $n$자리의 수를 만들 수 있고, 더 큰 수를 만든 사람이 이긴다.
Bob은 아직 어려서 어떻게 큰 수를 만드는지 잘 모른다. 대신, 자신이 가진 카드를 바닥에 좌우로 순서대로 나열한 뒤, 좌에서 우로 읽었을 때 만들어지는 수와 우에서 좌로 읽었을 때 만들어지는 수 중 아무 수나 고르는 전략을 택한다. 예를 들어, Bob이 바닥에 나열한 카드의 순서가 $[2, 3, 4]$ 라면 Bob은 좌-우 순서대로 $234$를 만들 수도 있고 혹은 우-좌 순서대로 $432$를 만들 수도 있다.
Alice는 동생인 Bob이 이기도록 해주고 싶어서 아래 규칙에 따라 플레이 하기로 했다:
- 먼저, Bob이 바닥에 카드를 내려 놓도록 기다린다.
- Bob이 좌-우 혹은 우-좌 둘 중 어떤 방법으로 수를 만들더라도 Bob이 만든 수가 Alice의 수 보다 크게 해서 동생이 이기게 해주고 싶다. 단, 카드를 최소 한 장은 사용해야 한다.
- Bob 이 이길 수 있도록 하는 방법 중 자신이 만들 수 있는 가장 큰 수를 만들고 싶다.
예를 들어 위의 예제의 경우 Bob은 $[2, 3, 4]$ 순서로 카드를 바닥에 나열했고, Alice가 가진 카드는 $[1, 2, 3]$이라 하자.
- Alice가 만들 수 있는 세 자리 수는 $123$, $132$, $213$, $231$, $312$, $321$로 총 여섯 가지가 있다.
- Bob 이 $234$와 $432$중 어떤 수를 만들지 모르므로, Alice가 $231$을 만들면 Bob이 어떤 수를 만들더라도 이기게 해줄 수 있고, 그 중 Alice가 만들 수 있는 가장 큰 수가 된다.
다른 예로, Bob이 $[2, 1, 2]$를 가지고 있고 Alice가 $[2, 2, 2]$를 가지고 있다하자.
- Bob이 만들 수 있는 수는 좌-우와 우-좌의 경우 모두 $212$로 같다.
- Alice가 만들 수 있는 세자리 수는 $222$로 $212$보다 크므로, Alice는 카드를 세 장 모두 사용해서는 Bob이 이기게 해줄 수 없다.
- Alice가 만들 수 있는 두자리 수는 $22$가 있고, 이 예제의 답이 된다.
입력으로 $n$과 두 사람이 가진 카드에 적힌 값이 주어졌을 때, Alice가 만들 수 있는 가장 큰 수를 구해보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 세 줄에 걸쳐 주어진다.
첫째 줄에 $n$이 주어진다.
둘째 줄에 Bob이 가진 카드에 적힌 숫자가 공백없이 주어진다. Bob이 이 순서대로 바닥에 카드를 내려놓는다.
셋째 줄에 Alice가 가진 카드에 적힌 숫자가 공백없이 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- $1 ≤ T ≤ 10$
- $2 ≤ n ≤ 8$
예제 입력 1
5 2 99 99 3 212 222 3 234 123 4 4123 2345 8 12345678 99999999
예제 출력 1
9 22 231 2543 9999999
- 예제 1: Alice가 99를 만들면 Bob이 만드는 수와 같아지므로 Bob이 이기게 해줄 수 없다.
- 예제 2: 본문에서 다루었다.
- 에제 3: 본문에서 다루었다.
- 예제 4: 추가 설명 없음.
- 예제 5: 추가 설명 없음.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호