5905번 - 악당 로봇 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 152 | 98 | 67 | 63.208% |
문제
슈퍼히어로 박승원은 결국 지구를 침략한 악당 로봇들을 해킹하는 데 성공했다. 로봇은 N개의 취약점을 가지고 있는데, (1 ≤ N ≤ 20) i번째 취약점은 'A', 'B', 'C' 로만 구성된 15자 이하의 문자열 Si 로 표현된다. 박승원 역시 로봇들을 'A', 'B', 'C' 버튼을 누르면서 공격할 수 있으며, 로봇의 취약점과 일치하도록 버튼을 누르면 공격에 성공하게 된다.
예를 들어 로봇의 취약점이 "ABA", "CB", "ABACB"라 하자. 박승원이 만약에 "ABACB"를 누르게 되면, 1 ~ 3번째 문자가 "ABA", 4 ~ 5번째 문자가 "CB", 전체가 "ABACB"와 매칭되어서 3번의 공격을 성공한 것과 같다. 이 예제에서 볼수 있다시피 여러개의 취약점을 한꺼번에 공격할 수 있으며, 또한 한 취약점을 여러 번 사용할 수도 있다.
우리의 슈퍼히어로 박승원에게는 시간이 없기 때문에 정확히 K번밖에 버튼을 누를 수 없다. (1 ≤ K ≤ 1000) 우리 모두 박승원을 도와 그가 공격할 수 있는 최대 횟수를 출력해주자.
입력
첫 번째 줄에는 N과 K가 주어지며, 이후 N개의 줄에 취약점 Si가 주어진다.
출력
박승원이 공격할 수 있는 최대 횟수를 출력한다.
예제 입력 1
3 7 ABA CB ABACB
예제 출력 1
4
힌트
ABACBCB 를 눌러 공격하면 ABA와 한번, ABACB와 한번, CB와 두번 매칭되어 총 4번 공격에 성공한다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호