외계 리보핵산
시간 제한2초메모리 제한512 MB
각 가닥에 대해 B-S와 C-F 염기쌍이 겹치지 않는 구간 접힘으로 최대 몇 개 결합할 수 있는지 구한다.
문제
외계 리보핵산(흔히 RNA라고 부른다)이 새로 발견되었다. 과학자들은 마땅한 이름이 떠오르지 않아 이 발견을 외계 리보핵산(RNAA)이라고 불렀다. 우리가 아는 RNA처럼 RNAA도 여러 염기로 이루어진 가닥이다. 염기는 B, C, F, S 네 종류이며 둘씩 짝을 지어 결합한다. 결합할 수 있는 쌍은 B와 S, 그리고 C와 F뿐이다.
RNAA는 활성화되면 가닥의 여러 구간을 접어 염기끼리 결합시킨다. 과학자들이 알아낸 사실은 다음과 같다.
- 가닥의 한 구간이 접히면 그 구간에 있는 모든 염기가 짝이 되는 염기와 결합한다.
- 각 염기는 다른 염기 하나와만 결합할 수 있다.
- 접힘은 가닥에서 만들어지는 결합의 수가 최대가 되도록 일어난다.
아래 그림은 가닥이 접히면서 결합이 생기는 모습이다.
RNAA 가닥이 주어질 때, 이 가닥이 활성화되면 염기 사이에 결합이 몇 개 생기는지 구하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며 파일의 끝(EOF)에서 끝난다. 각 테스트 케이스는 한 줄이며, RNAA 가닥의 염기 서열이 주어진다. 가닥의 길이는 1 이상 300 이하이다. 염기 사이에는 공백이 없고, 각 염기는 B, C, F, S 중 하나이다.
출력
각 테스트 케이스마다 주어진 가닥이 활성화될 때 생기는 결합의 총 개수를 한 줄에 출력한다.