문제
소 Bessie는 자신이 가장 좋아하는 초원 한가운데 있는 거대한 돌에 새겨진 신비로운 비문을 발견했다. 이 비문의 문자는 오직 C, O, W 세 글자로만 이루어져 있으며, 고대 암호 같은 언어로 되어 있다.
Bessie는 이 문자를 해독할 수 없지만, C, O, W가 순서대로 나열된 “COW”가 자신이 가장 좋아하는 단어라는 사실을 알고 있다. 따라서 “COW”가 이 비문 안에서 몇 번 나타나는지 궁금해졌다.
Bessie는 “COW”가 정확히 연속된 형태로 나타나는지에는 신경 쓰지 않는다. 글자 순서만 유지되면, 다른 문자가 사이에 끼어 있어도 괜찮다. 또한, 서로 다른 “COW”가 일부 문자를 공유해도 상관없다.
예를 들어:
• “CWOW”에는 “COW”가 1번 포함된다.
• “CCOW”에는 “COW”가 2번 포함된다.
• “CCOOWW”에는 “COW”가 8번 포함된다.
비문의 내용이 주어졌을 때, “COW”가 몇 번 등장하는지 계산하라.
입력
첫 번째 줄에는 정수
두 번째 줄에는 길이 $N$의 문자열이 주어진다. 문자열의 모든 문자는 C, O, W 중 하나이다.
출력
문자열 내에서 “COW”가 부분 수열(subsequence) 형태로 등장하는 횟수를 출력하라.
문제의 답은
예제1
입력
6
COOWWW
출력
6
출처
USACO 2015 February Bronze