https://www.acmicpc.net/problem/31778
문제요약
- 문자열 S가 주어짐. C와 P로만 이루어졌고 길이 20만
- 두 위치를 바꿀 수 있음. 최대 K번(20만)
- PPC 부분문자열의 최대 개수 구하기
접근법
- PPPPPP...CCCC 이런 형식은 PPC 부분 문자열이 최대일 것임
- 왼쪽에서 적당히 P를 구하고 오른쪽에서 C를 구하면 되니까
- 잘 생각해보면 가능하면 왼쪽으로 P를 몰고, 오른쪽에 C를 몰면 유리함
- 즉 C와 P를 최대한 교환하면 유리함
- 이후 C가 나올때 마다 왼쪽에 나왔던 P의 개수를 이용해서 PPC 부분 문자열의 수를 구함
- PPPP....를 적당히 조합하면 PP가 되는데 이 개수를 구하는 것은 쉬움
newbieski