레이팅 미적용카운티 축제에서 최고의 소 사진작가 상을 받고 싶어 안달이 난 농부 존은, 자신의 \(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'는 건지를 나타낸다.
필요한 최소 뒤집기 횟수를 한 줄에 출력한다.
14
GGGHGHHGHHHGHG1In this example, it suffices to reverse the prefix consisting of the first six
cows.
GGGHGHHGHHHGHG (Before)
-> HGHGGGHGHHHGHG (After)
Before the reversal, four Guernseys were at even positions. After the reversal,
six Guernseys are at even positions. It is impossible for there to be more than
six Guernseys at even positions.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Bronze