짧은 모음
면접 대비시간 제한1초메모리 제한1024 MB
단어의 부분 수열 중에서 짧은 모음(모음 뒤에 자음이 두 개 이상 오는 경우)이 없는 것의 개수를 센다. 전체 단어와 빈 문자열은 제외한다.
문제
알고리즘 문제를 푸는 것도 어렵지만, 종종 더 어려운 일은 테스트 데이터를 준비하는 것이다. 문제 Arabiska를 예로 들어 보자. 여기서는 출제진이 많은 시간 동안 hej vad heter du 같은 걸작을 만들기 위해 노력했다.
여기서 떠오르는 질문은: 짧은 모음을 포함하지 않는 문자열을 어떻게 만들까? Arabiska 문제를 읽었다면, 짧은 모음이란 최소 두 개의 자음이 뒤따르는 모음이라는 것을 기억할 것이다. 단어 tall에서 a는 짧은 모음이고, potatis에는 짧은 모음이 없다. 편의상 이 문제에서는 a, e, i, o, u, y를 모음으로 간주한다.
짧은 모음이 없는 단어를 만드는 한 가지 방법은 단어에서 몇 글자를 지우는 것이다. potatis에서 시작하면 예를 들어 ptais를 얻을 수 있다. 하지만 결과가 otats가 되면 짧은 모음이 생긴다.
주어진 단어에서 글자를 지워 결과에 짧은 모음이 없도록 하는 방법의 수를 세는 것이 과제이다. 글자를 하나도 지우지 않는 것도 허용된다(두 번째 예제에서는 이것이 답에 을 더한다). 반면 모든 글자를 지우는 것은 허용되지 않는다. 같은 단어가 서로 다른 글자 집합을 지워서 만들어지면 각각 따로 센다(첫 번째 예제에서는 tal을 만드는 두 가지 방법이 있다. 첫 번째 또는 두 번째 l을 지울 수 있다).
입력
입력은 최대 글자의 단어 한 줄로 이루어진다. 단어는 a-z 글자로만 구성된다.
출력
짧은 모음이 없는 단어가 되도록 글자를 지우는 방법의 수를 정수로 출력한다.
답이 항상 비트 정수에 들어가는 것은 아니다.