34803번 - 문자열 로또 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 206 | 174 | 159 | 86.413% |
문제
DGIST 나라에는 문자열을 이용한 로또가 있다.
로또의 규칙은 아래와 같다.
- 구매
- 로또를 구매할 때 알파벳 대문자만으로 구성된 길이 $L$의 문자열을 $N$개 작성한다.
- 추첨
- 알파벳 대문자로만 구성된 길이 $K$의 문자열 $s$를 추첨한다.
- 구매 시 작성한 문자열의 모든 부분 문자열 중 $s$와 같은 것의 개수를 점수로 얻는다. 총점수는 구매 시 작성한 모든 문자열에 대한 점수의 총합이다.
- 여기서 부분 문자열이란, 문자열의 연속된 일부를 말한다.
aek,joo,ekj는baekjoon의 부분 문자열이고,bak,p,oone는 부분 문자열이 아니다.
달구는 이번 주에 이 로또를 하나 구매했다. 달구가 이번 주 로또 추첨에서 얻을 수 있는 총 점수의 최댓값을 구하시오.
입력
첫 번째 줄에, 로또에 들어 있는 문자열의 길이 $L$과 문자열의 개수 $N$이 공백으로 구분되어 정수로 주어진다. ($1 \le L \le 100$; $1 \le N \le 20$)
다음 $N$개의 줄에 걸쳐, 달구가 이번 주에 구매한 로또에 작성한 문자열이 한 줄에 하나씩 주어진다. (주어지는 문자열은 알파벳 대문자로만 이루어져있다.)
$N+2$ 번째 줄에 정수 $K$가 주어진다. ($1 \le K \le L$)
출력
첫 번째 줄에 달구가 이번 주 로또 추첨에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
예제 입력 1
6 4 ABABAB AABBAA AABBBB ABBAAB 2
예제 출력 1
7
문자열 AB가 추첨된다면, ABABAB에서 $3$점,AABBAA에서 $1$점, AABBBB에서 $1$점, ABBAAB에서 $2$점을 얻어 총 $7$점을 얻을 수 있다. 이는 가능한 최대이다.
예제 입력 2
4 1 ZZZZ 2
예제 출력 2
3
문자열 ZZ가 추첨된다면, ZZZZ에서 ZZZZ, ZZZZ, ZZZZ로 총 3점을 얻는다.
출처
University > DGIST > 2025 DGIST 알고리즘 경진대회 B번
- 문제를 만든 사람: haruki291sa
- 문제를 검수한 사람: ksoosung77, leo020630, tlsdydaud1, tony9402