| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 72 | 38 | 36 | 56.250% |
빈 문자열이 아닌 문자열 $T$에 대해, unique($T$)는 $T$의 연속된 동일한 문자들을 하나만 남기고 제거한 문자열이다. 예를 들어, unique(ABBCCCBBA)는 ABCBA이다.
지훈이는 주어진 문자열 $S$에 최소 횟수의 인접 교환 연산을 통해 unique($S^\prime$)이 KCPC가 되는 문자열 $S^\prime$을 만들고 싶다. 여기서 인접 교환 연산이란 문자열에서 서로 인접해 있는 두 문자 한 쌍의 위치를 서로 바꾸는 연산을 의미한다.
문자열 $S$가 주어졌을 때, unique($S^\prime$)이 KCPC가 되는 데 필요한 인접 교환 연산의 최소 횟수를 구해보자.
첫 번째 줄에 K, C, P로만 이루어진 문자열 $S(4\le\lvert S\rvert\le 10^6)$가 주어진다.
유한한 인접 교환 연산을 통해 unique($S^\prime$)이 KCPC가 될 수 있는 경우만 주어진다.
첫 번째 줄에 unique($S^\prime$)이 KCPC가 되는 데 필요한 인접 교환 연산의 최소 횟수를 출력한다.
KCPC
0
unique(KCPC)는 KCPC이다.
CPCK
3
아래와 같이 총 $3$번의 인접 교환 연산으로 문자열 KCPC를 만들 수 있으며, unique(KCPC)는 KCPC이다.
CPCK $\rightarrow$ CPKC $\rightarrow$ CKPC $\rightarrow$ KCPC
KCPCKCPC
5
총 $5$번의 인접 교환 연산으로 문자열 KKCCPPCC를 만들 수 있으며, unique(KKCCPPCC)는 KCPC이다.
CKCCKCCKPCKPCKPCCCCCKP
48
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 2 H번