20915번 - 숫자 카드 놀이 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 264 | 97 | 80 | 39.801% |
문제
Albert 는 n장의 숫자 카드를 가지고 있다. 각 카드에는 0부터 9까지 숫자 하나씩이 적혀있고, 6이나 9가 적힌 카드를 회전할 경우 구분할 수 없다 (즉, 6이 적힌 카드는 회전하면 9로 보이고, 9가 적힌 카드는 회전하면 6으로 보인다).
Albert는 최근 두 수의 곱셈에 대해 배운터라 n장의 카드를 모두 이용하여 두 개의 수를 만든 후, 그 수의 곱이 최대가 되도록 하고 싶다. 단, n장의 카드 모두 사용하여야 하며, 각 수는 최소 1장 (그리고 최대 n-1장)의 카드로 구성되어야 한다. 6이나 9가 적힌 카드는 Albert가 임의로 회전하여 사용할 수 있다.
예를 들어 n = 8이고 Albert가 가진 카드가 [2, 0, 2, 0, 2, 0, 2, 1] 이라 하자. 이 때 8장의 카드를 활용하여 "2200" 과 "2210"을 만들면 두 수의 곱은 4862000이 된다. 혹은 "2020"과 "2021"을 만들어 곱이 4082420이 되도록 할 수도 있다. 이 예제에서 Albert가 만들 수 있는 최대 곱은 4862000이다.
입력으로 Albert가 가진 n장의 숫자 카드가 주어졌을 때, 달성 가능한 최대 곱을 구하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
다음 각 줄에 Albert가 가진 숫자 카드를 표현하는 문자열이 (공백없이) 주어지는데, 문자열의 각 문자는 '0'-'9' 중 하나이다.
출력
각 테스트 케이스에 대해 Albert가 만들 수 있는 최대 곱을 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 18
- 모든 입력에 대해 정답은 항상 1018 이하인 입력만 주어진다.
예제 입력 1
5 90000 66 102030 20202021 999999999999999999
예제 출력 1
0 81 63000 4862000 999999998000000001
케이스 1: 어떻게 나누더라도 두 수 중 한 수는 0이 된다.
케이스 2: 6이 적힌 카드 두 장을 회전하여 9*9 = 81 을 얻을 수 있다.
케이스 3: 21000 * 3 = 63000.
케이스 4: 본문에서 다루었다.
케이스 5: 999999999 * 999999999 = 999999998000000001.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호