1683번 - 책장 맨 윗칸 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 48 | 9 | 7 | 15.217% |
문제
데이브 존슨은 책 수집가이다. 오랜 세월이 지난 후 그는 너무 많은 책들을 모아서 새 책장을 사기로 결심했다. 그는 품질이 모두 다른 여러개의 책장을 샀는데, 문제는 그가 가장 좋아하는 책들을 가장 좋은 책장의 맨 위에 놓고 싶었다는 것이다. 이 책장의 한 칸은 최대 10개의 책을 넣을 수 있다.
그러나 괴짜인 데이브는 가장 좋아하는 책들을 정렬하는 특별한 방법이 있다. 그 책들은 당연히 알파벳 순서로 정렬되어 있어야 하지만, 또한 같은 알파벳이 제목의 같은 위치에 있는 책은 붙어 있으면 안 된다는 것이 문제. 또 중요한 것은 데이브는 오직 알파벳 문자만 문자로 치고, 띄어쓰기나 쉼표, `등은 문자로 치지 않는다는 것이다. 그러므로 "Portnoy's Complaint"라는 제목에서 's'는 8번째 문자이고, 'c'는 9번째 문자이다. 문제에 대한 예를 들자면 "The Grapes Of Wrath" 라는 제목의 책과 "One Flew Over The Cuckoo's Nest" 라는 제목의 책은 서로 붙어 있을 수 없는데, 그것은 두 제목의 세 번째 문자가 공통적으로 'e'이기 때문이다.
이 문제를 해결하려는 우리들을 도와주기 위해서(혹은 문제를 더 어렵게 만들기 위해서), 데이브는 '선호도 지수'라는 것을 모든 책들에 부여했다. 주어지는 책들과 선호도 지수의 목록을 활용해 데이브에게 그가 책장의 가장 윗 칸에 놓게 되는 책들의 목록을 알려 주자. 맨 윗 칸에 놓인 책들의 선호도 지수의 합이 가장 크게 만들어야 한다.
입력
입력 파일마다 한 개의 테스트 케이스가 있다. 입력의 첫줄에는 데이브의 책장 맨 윗칸 후보에 올라있는 책들의 개수 N(10 ≤ N ≤ 2500)이, 그 뒤의 N개의 줄은 각각 책의 선호도 지수 E와 책의 제목 S가 한 칸의 띄어쓰기로 구별되어 입력되고, E는 200 이하의 자연수이며 S는 문자열이며 30문자를 넘지 않는다. S에는 적어도 하나의 알파벳 문자가 포함되어 있다. 입력은 stdin 형식이다.
출력
출력의 첫째 줄은 데이브의 맨 윗칸에 놓을 책의 개수인 정수 M을 출력해야 하며, 두 번째 줄은 맨 윗 칸의 모든 책들의 선호도 지수의 합이어야 하고, 다음 M개의 줄은 맨 윗 칸에 놓을 책들의 제목이 사전식 순서로 정렬되어 출력되어야 한다. 한 개보다 많은 정답이 존재할 경우 아무 것이나 출력해도 상관 없다. 출력은 stdout 형식이어야 한다.
예제 입력 1
12 117 The Pearl 42 L'Etranger 135 Hamlet 100 War And Peace 55 The Prince 175 Of Mice And Men 200 The Grapes Of Wrath 120 Ulysses 87 For Whom The Bell Tolls 10 Oliver Twist 50 Snow Crash 110 Great Expectations
예제 출력 1
8 969 For Whom The Bell Tolls Great Expectations Hamlet L'Etranger Of Mice And Men The Grapes Of Wrath Ulysses War And Peace
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호