시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 133 | 85 | 74 | 69.159% |
초등학생 준석이는 영어를 배우고 있는 중이다.
개구쟁이인 준석이는 단어에서 본인이 마음에 드는 부분을 뽑아 섞어 읽고, 뽑은 부분의 알파벳 종류와 개수만 이야기한다.
준석이와 소통하고 싶어하는 진우 선생님은 준석이가 일정한 규칙을 가지고 읽는다는 것을 깨달았다.
진우 선생님이 발견한 규칙은 다음과 같다.
먼저, 준석이는 주어진 단어에서 본인이 읽고 싶은 연속된 문자열을 뽑아 다음의 규칙에 따라 새 문자열을 만든다.
위의 규칙에 따라 여러 문자열들을 만들 수 있는데 만약 만들어진 문자열이 중복되면, 오직 1개만 가능한 문자열로 생각한다.
또한 반으로 나눌 문자열 S의 길이가 N이라 하면, N이 홀수일 경우 반으로 나누는 방법은 두 가지가 생긴다.
이 경우, 두 가지를 모두 가능한 방법으로 생각하며 두 가지 방법에서 발생하는 모든 경우의 수도 포함해야 한다.
이런 규칙에 따라 새 문자열을 만들고 나면 준석이는 그 문자열에 포함된 알파벳과 알파벳의 개수를 말한다. (단, 준석이가 잘못 말할 가능성은 없다.)
예를 들어, inconvenience라는 단어가 주어졌다고 하자.
준석이는 e가 2개, n이 2개, i가 1개, c가 1개라고 말한다.
준석이가 말한 조건에 따르면, 준석이가 단어 속에서 뽑은 연속된 문자열은 두 개가 될 수 있다.(enienc, nience)
예시를 위해 enienc를 봤다고 가정하자.
이처럼 inconvenience라는 단어가 주어지고, 준석이가 단어 속에서 뽑은 연속된 문자열 enienc과 nience에 대하여
준석이의 규칙에 의해 만들어진 문자열들은 eincne, einnce, einnec, enicne, ineecn, ineenc, inenec, neicne, neiecn, nieecn으로 총 10개다.
진우 선생님은 준석이와 소통을 하기 위해 준석이의 규칙에 의해 만들어질 문자열들을 모두 알아내고자 한다.
진우 선생님을 도와 주어진 단어, 준석이가 말한 알파벳과 알파벳들의 개수를 토대로 규칙에 따라 만들 수 있는 문자열들의 개수를 출력하는 프로그램을 만들자.
첫째 줄에 준석이가 말한 알파벳 종류의 개수가 주어진다. 단, 알파벳 종류의 개수는 N개(0 < N < 15)다.
둘째 줄에는 준석이가 말한 알파벳들과 각각의 개수가 주어진다. 단, 각각의 개수는 M개(0 < M < 15)다.
세번째 줄에는 알파벳 소문자로 이루어진 영어 단어가 주어진다. 단, 영어 단어의 길이는 알파벳 각각의 갯수들의 합 이상이며 15자 미만이다.
규칙에 따라 만들 수 있는 문자열의 개수를 출력한다. 단, 중복되는 문자열일 경우 그 문자열은 1개로 취급해야 한다.
4 c 1 e 2 i 1 n 2 inconvenience
10
만들 수 있는 문자열 : eincne, einnce, einnec, enicne, ineecn, ineenc, inenec, neicne, neiecn, nieecn
5 a 1 e 1 g 1 r 1 t 1 great
7
만들 수 있는 문자열 : ergat, gerta, greta, grtae, rgaet, rgeat, rgeta
University > 중앙대학교 > 2019 중앙대학교 프로그래밍 경진대회(CPC) C번