KOREA 문자열 만들기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

K, O, R, E, A로만 이루어진 문자열이 주어질 때, 일부 문자를 지워 K로 시작해 K, O, R, E, A 순서가 반복되는 가장 긴 부분 수열의 길이를 구한다.

난이도: 보통10점 중 4점
유형: 문자열, 그리디, 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

고려대학교의 영문 이름은 KOREA UNIVERSITY이다.

영어 알파벳 대문자 K, O, R, E, A로만 이루어진 문자열 $S$ 가 주어진다. $S$ 에서 $0$ 개 이상의 문자를 지웠을 때 “KOREAKOREAKOR” 처럼 ‘K’로 시작하고 각 글자가 ‘K’, ‘O’, ‘R’, ‘E’, ‘A’ 순서로 반복되는 문자열을 만들려고 한다. 이를 KOREA 문자열이라고 하자.

문자열이 주어졌을 때, $0$ 개 이상의 문자를 지워서 만들 수 있는 가장 긴 KOREA 문자열의 길이를 구하여라.

입력

첫 번째 줄에 문자열 $S$ 가 주어진다. $S$ 는 영어 알파벳 대문자 K, O, R, E, A로만 이루어져 있으며, 문자열의 길이는 $10$ 이상 $1\\,000$ 이하이다.

출력

첫 번째 줄에 만들 수 있는 가장 긴 KOREA 문자열의 길이를 출력한다.

예제3

예제 1
입력
```
KEKRORKAKROEKREORKA
```
예상 출력
```
5
```
예제 2
입력
```
OOOOOOOREA
```
예상 출력
```
0
```
예제 3
입력
```
KEROKRKKAKAOA
```
예상 출력
```
3
```