24431번 - 유사 라임 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 168 | 129 | 100 | 78.125% |
문제
Alice는 영어 단어를 조합하여 라임(Rhyme)을 만드는 단어 게임을 즐겨한다. Bob도 라임을 만들고 싶지만, 아직 어려서 단어를 잘 모르기 때문에 Alice가 "유사 라임 게임"을 제안했다.
먼저, 영문 대문자로만 구성된 길이가 $L$인 서로 다른 단어 $n$개를 종이에 적는다: 편의상 $W_1, W_2, \dots W_n$을 $n$개의 단어라 하자.
어떤 한 쌍의 단어 $W_i$와 $W_j$를 비교했을 때 최대 공통 접미사의 길이가 $F$이상이면 두 단어는 "유사 라임"을 이룬다고 정의한다. 이러한 단어 쌍을 "유사 라임 쌍"이라 부르자.
"유사 라임 게임"은 주어진 단어들을 이용하여 최대한 많은 "유사 라임 쌍"을 만드는 게임이다. 단, 한 단어는 최대 하나의 유사 라임 쌍에만 속할 수 있다.
예를 들어 $n = 4$, $L = 4$일때, $4$개의 단어가 다음과 같다고 하자: $W_1 =$ "WALK", $W_2 =$ "TALK", $W_3 =$ "MILK", $W_4 =$ "BULK".
- 만약 $F ≤ 2$라면, 아무렇게나 두 쌍으로 묶어도 유사 라임 쌍이 되므로 $2$개의 쌍을 찾을 수 있다. 예를 들면 ("
WALK", "BULK"), ("TALK","MILK")가 있다. - 만약 $F = 3$라면, ("
WALK", "TALK")를 묶어 하나의 유사 라임 쌍을 만들 수 있지만, $2$개 이상을 만들 방법은 없다. - 만약 $F ≥ 4$라면, 유사 라임 쌍을 만들 방법은 없다.
입력으로 $F$ 그리고 길이가 $L$인 $n$개의 단어가 주어졌을 때, Bob이 만들 수 있는 최대 개수의 "유사 라임 쌍"이 몇 개인지 구해보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 입력은 두 줄에 걸쳐 주어진다. 첫 줄에 $n$, $L$, $F$가 공백으로 구분되어 주어진다. 둘째 줄에 영문 대문자로만 구성된 길이 $L$인 문자열 $n$개 $W_1, W_2, \dots W_n$이 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- $1 ≤ T ≤ 10$
- $1 ≤ F ≤ L ≤ 10$
- $2 ≤ n ≤ 500$
- 각 문자열 $W_i$는 알파벳 대문자로만 구성되어 있다.
- 각 테스트 케이스에 주어지는 $n$개의 문자열은 중복되지 않는다.
예제 입력 1
5 4 4 2 WALK TALK MILK BULK 4 4 3 WALK TALK MILK BULK 4 4 4 WALK TALK MILK BULK 6 3 1 AXB BCC DEE XBB YCC ZEE 6 3 2 AXB BCC DEE XBB YCC ZEE
예제 출력 1
2 1 0 3 2
예제 1-3: 본문에서 다루었다.
예제 4-5: 추가 설명 없음.
힌트
최대 공통 접미사: 두 문자열의 공통 접미사 (common suffix)중 가장 길이가 긴 공통 접미사를 의미한다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호