26201번 - Finding Maximal Non-Trivial Monotones
이 문제에서는 문자열이라고도 불리는 문자 시퀀스를 다룹니다.
시퀀스는 원소가 2개 이상일 때 **비자명(non-trivial)**하다고 합니다.
시퀀스 s가 주어졌을 때, 부분 시퀀스 si,…,sj의 모든 문자가 동일하면 **단조(monotone)**하다고 하고,
단조성을 유지하면서 왼쪽 또는 오른쪽으로 더 이상 확장할 수 없을 때 **극대(maximal)**하다고 합니다.
"a"와 "b"로만 이루어진 시퀀스가 주어졌을 때, 비자명한 극대 단조 부분 시퀀스에 속하는 문자 "a"의 개수를 구하세요.
입력
입력은 두 줄로 이루어집니다.
첫 번째 줄에는 정수 N(1≤N≤10**5)이 주어집니다.
두 번째 줄에는 "a"와 "b"로만 이루어진 길이 N의 문자열이 주어집니다.
출력
비자명한 극대 단조 부분 시퀀스에서 문자 "a"가 등장하는 총 횟수를 한 줄에 출력합니다.
Note. 비자명한 극대 단조 부분 시퀀스와 같은 단어 해석에 시간을 쓰지 말고,
길이 2 이상인 연속된 "a" 그룹에 속한 "a"의 갯수를 더하라는 말입니다.
댓글을 작성하려면 로그인해야 합니다.
qkrekgka2003 8달 전
이 문제에서는 문자열이라고도 불리는 문자 시퀀스를 다룹니다.
시퀀스는 원소가 2개 이상일 때 **비자명(non-trivial)**하다고 합니다.
시퀀스 s가 주어졌을 때, 부분 시퀀스 si,…,sj의 모든 문자가 동일하면 **단조(monotone)**하다고 하고,
단조성을 유지하면서 왼쪽 또는 오른쪽으로 더 이상 확장할 수 없을 때 **극대(maximal)**하다고 합니다.
"a"와 "b"로만 이루어진 시퀀스가 주어졌을 때, 비자명한 극대 단조 부분 시퀀스에 속하는 문자 "a"의 개수를 구하세요.
입력
입력은 두 줄로 이루어집니다.
첫 번째 줄에는 정수 N(1≤N≤10**5)이 주어집니다.
두 번째 줄에는 "a"와 "b"로만 이루어진 길이 N의 문자열이 주어집니다.
출력
비자명한 극대 단조 부분 시퀀스에서 문자 "a"가 등장하는 총 횟수를 한 줄에 출력합니다.
Note. 비자명한 극대 단조 부분 시퀀스와 같은 단어 해석에 시간을 쓰지 말고,
길이 2 이상인 연속된 "a" 그룹에 속한 "a"의 갯수를 더하라는 말입니다.