사진 촬영

카운티 축제에서 최고의 소 사진작가 상을 받고 싶어 안달이 난 농부 존은, 자신의 \(N\)마리 소(\(2 \leq N \leq 2\cdot 10^5\), \(N\)은 짝수)의 완벽한 사진을 찍으려 하고 있다.

농부 존은 두 가지 품종의 소를 기른다. 건지와 홀스타인이다. 사진을 최대한 아름답게 만들기 위해, 그는 줄에서 짝수 번째 위치에 최대한 많은 건지가 오도록 소들을 세우고 싶다(줄의 첫 번째 위치는 홀수 위치, 그다음은 짝수 위치, 이런 식이다). 소들과의 의사소통이 원활하지 않은 탓에, 그가 목표를 달성할 수 있는 유일한 방법은 소들의 짝수 길이 "접두사"에게 스스로 뒤집으라고 요청하는 것뿐이다(접두사는 첫 번째 소부터 어떤 위치 \(j\)의 \(j\)번째 소까지의 소들의 구간이다).

농부 존이 목표를 달성하는 데 필요한 최소 뒤집기 횟수를 구하여라.

Problem credits: Aryansh Shrivastava

채점 방식

• 테스트 케이스 2-6은 \(N\le 1000\)을 만족한다.
• 테스트 케이스 7-11은 추가 제약이 없다.

Problem credits: Aryansh Shrivastava

첫째 줄에 \(N\)의 값이 주어진다.

둘째 줄에는 소들의 초기 배치를 왼쪽에서 오른쪽 순서로 나타내는 길이 \(N\)의 문자열이 주어진다. 각 'H'는 홀스타인을, 각 'G'는 건지를 나타낸다.

필요한 최소 뒤집기 횟수를 한 줄에 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > US Open > Bronze