시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)72383656.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가 되는 데 필요한 인접 교환 연산의 최소 횟수를 출력한다.

예제 입력 1

KCPC

예제 출력 1

0

unique(KCPC)는 KCPC이다.

예제 입력 2

CPCK

예제 출력 2

3

아래와 같이 총 $3$번의 인접 교환 연산으로 문자열 KCPC를 만들 수 있으며, unique(KCPC)는 KCPC이다.

CPCK $\rightarrow$ CPKC $\rightarrow$ CKPC $\rightarrow$ KCPC

예제 입력 3

KCPCKCPC

예제 출력 3

5

총 $5$번의 인접 교환 연산으로 문자열 KKCCPPCC를 만들 수 있으며, unique(KKCCPPCC)는 KCPC이다.

예제 입력 4

CKCCKCCKPCKPCKPCCCCCKP

예제 출력 4

48
W3sicHJvYmxlbV9pZCI6IjM1MTU5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoidW5pcXVlKHN0cik9S0NQQyIsImRlc2NyaXB0aW9uIjoiPHA+XHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHViYjM4XHVjNzkwXHVjNWY0ICRUJFx1YzVkMCBcdWIzMDBcdWQ1NzQsIHVuaXF1ZSgkVCQpXHViMjk0ICRUJFx1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViM2Q5XHVjNzdjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YjRlNFx1Yzc0NCBcdWQ1NThcdWIwOThcdWI5Y2MgXHViMGE4XHVhZTMwXHVhY2UwIFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIHVuaXF1ZSg8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+QUJCQ0NDQkJBPFwvY29kZT48XC9zcGFuPilcdWIyOTQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkFCQ0JBPFwvY29kZT48XC9zcGFuPlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVkNmM4XHVjNzc0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFMkXHVjNWQwIFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWM3NTggPHN0cm9uZz5cdWM3NzhcdWM4MTEgXHVhZDUwXHVkNjU4IFx1YzVmMFx1YzBiMDxcL3N0cm9uZz5cdWM3NDQgXHVkMWI1XHVkNTc0IHVuaXF1ZSgkU15cXHByaW1lJClcdWM3NzQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktDUEM8XC9jb2RlPjxcL3NwYW4+XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFNeXFxwcmltZSRcdWM3NDQgXHViOWNjXHViNGU0XHVhY2UwIFx1YzJmNlx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIDxzdHJvbmc+XHVjNzc4XHVjODExIFx1YWQ1MFx1ZDY1OCBcdWM1ZjBcdWMwYjA8XC9zdHJvbmc+XHVjNzc0XHViNzgwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWMxMWNcdWI4NWMgXHVjNzc4XHVjODExXHVkNTc0IFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHViYjM4XHVjNzkwIFx1ZDU1YyBcdWMzMGRcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzExY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0ICRTJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCB1bmlxdWUoJFNeXFxwcmltZSQpXHVjNzc0IDxjb2RlPktDUEM8XC9jb2RlPlx1YWMwMCBcdWI0MThcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyA8c3Ryb25nPlx1Yzc3OFx1YzgxMSBcdWFkNTBcdWQ2NTggXHVjNWYwXHVjMGIwPFwvc3Ryb25nPlx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LPFwvY29kZT48XC9zcGFuPiwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkM8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UDxcL2NvZGU+PFwvc3Bhbj5cdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCAkUyg0XFxsZVxcbHZlcnQgU1xccnZlcnRcXGxlIDEwXjYpJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcyMFx1ZDU1Y1x1ZDU1YyA8c3Ryb25nPlx1Yzc3OFx1YzgxMSBcdWFkNTBcdWQ2NTggXHVjNWYwXHVjMGIwPFwvc3Ryb25nPlx1Yzc0NCBcdWQxYjVcdWQ1NzQgdW5pcXVlKCRTXlxccHJpbWUkKVx1Yzc3NCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+S0NQQzxcL2NvZGU+PFwvc3Bhbj5cdWFjMDAgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCB1bmlxdWUoJFNeXFxwcmltZSQpXHVjNzc0IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPlx1YWMwMCBcdWI0MThcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyA8c3Ryb25nPlx1Yzc3OFx1YzgxMSBcdWFkNTBcdWQ2NTggXHVjNWYwXHVjMGIwPFwvc3Ryb25nPlx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+dW5pcXVlKDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPilcdWIyOTQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktDUEM8XC9jb2RlPjxcL3NwYW4+XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5cdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Y2QxZCAkMyRcdWJjODhcdWM3NTggPHN0cm9uZz5cdWM3NzhcdWM4MTEgXHVhZDUwXHVkNjU4IFx1YzVmMFx1YzBiMDxcL3N0cm9uZz5cdWM3M2NcdWI4NWMgXHViYjM4XHVjNzkwXHVjNWY0IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPlx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgdW5pcXVlKDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPilcdWIyOTQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktDUEM8XC9jb2RlPjxcL3NwYW4+XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+Q1A8c3Ryb25nPkNLPFwvc3Ryb25nPjxcL2NvZGU+PFwvc3Bhbj4gJFxccmlnaHRhcnJvdyQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkM8c3Ryb25nPlBLPFwvc3Ryb25nPkM8XC9jb2RlPjxcL3NwYW4+ICRcXHJpZ2h0YXJyb3ckIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT48c3Ryb25nPkNLPFwvc3Ryb25nPlBDPFwvY29kZT48XC9zcGFuPiAkXFxyaWdodGFycm93JCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+S0NQQzxcL2NvZGU+PFwvc3Bhbj48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHA+XHVjZDFkICQ1JFx1YmM4OFx1Yzc1OCA8c3Ryb25nPlx1Yzc3OFx1YzgxMSBcdWFkNTBcdWQ2NTggXHVjNWYwXHVjMGIwPFwvc3Ryb25nPlx1YzczY1x1Yjg1YyBcdWJiMzhcdWM3OTBcdWM1ZjQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktLQ0NQUENDPFwvY29kZT48XC9zcGFuPlx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgdW5pcXVlKDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LS0NDUFBDQzxcL2NvZGU+PFwvc3Bhbj4pXHViMjk0IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzNTE1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InVuaXF1ZShzdHIpPUtDUEMiLCJkZXNjcmlwdGlvbiI6IjxwPkZvciBhIG5vbi1lbXB0eSBzdHJpbmcgJFQkLCB1bmlxdWUoJFQkKSBpcyB0aGUgc3RyaW5nIG9idGFpbmVkIGJ5IHJlbW92aW5nIGNvbnNlY3V0aXZlIGlkZW50aWNhbCBjaGFyYWN0ZXJzIGluICRUJCB3aGlsZSBsZWF2aW5nIG9ubHkgb25lIGZyb20gZWFjaCBydW4uIEZvciBleGFtcGxlLCB1bmlxdWUoPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkFCQkNDQ0JCQTxcL2NvZGU+PFwvc3Bhbj4pIGlzIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5BQkNCQTxcL2NvZGU+PFwvc3Bhbj4uPFwvcD5cclxuXHJcbjxwPkppaHVuIHdhbnRzIHRvIG9idGFpbiBhIHN0cmluZyAkU15cXHByaW1lJCBmcm9tIHRoZSBnaXZlbiBzdHJpbmcgJFMkIHVzaW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiA8c3Ryb25nPmFkamFjZW50IHN3YXAgb3BlcmF0aW9uczxcL3N0cm9uZz4gc3VjaCB0aGF0IHVuaXF1ZSgkU15cXHByaW1lJCkgYmVjb21lcyA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+S0NQQzxcL2NvZGU+PFwvc3Bhbj4uIEFuIDxzdHJvbmc+YWRqYWNlbnQgc3dhcCBvcGVyYXRpb248XC9zdHJvbmc+IG1lYW5zIHN3YXBwaW5nIHRoZSBwb3NpdGlvbnMgb2YgYSBwYWlyIG9mIGNoYXJhY3RlcnMgdGhhdCBhcmUgYWRqYWNlbnQgaW4gdGhlIHN0cmluZy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBzdHJpbmcgJFMkLCBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiA8c3Ryb25nPmFkamFjZW50IHN3YXAgb3BlcmF0aW9uczxcL3N0cm9uZz4gcmVxdWlyZWQgdG8gbWFrZSB1bmlxdWUoJFNeXFxwcmltZSQpIGJlY29tZSA8Y29kZT5LQ1BDPFwvY29kZT4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSwgYSBzdHJpbmcgJFMoNFxcbGVcXGx2ZXJ0IFNcXHJ2ZXJ0XFxsZSAxMF42KSQgY29uc2lzdGluZyBvbmx5IG9mIHNwYW4gc3R5bGU9JnF1b3Q7Y29sb3I6I2U3NGMzYzsmcXVvdDsmZ3Q7PGNvZGU+SzxcL2NvZGU+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+QzxcL2NvZGU+PFwvc3Bhbj4sIGFuZCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UDxcL2NvZGU+PFwvc3Bhbj4gaXMgZ2l2ZW4uPFwvcD5cclxuXHJcbjxwPk9ubHkgY2FzZXMgd2hlcmUgdW5pcXVlKCRTXlxccHJpbWUkKSBjYW4gYmVjb21lIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPiB1c2luZyBhIGZpbml0ZSBudW1iZXIgb2YgPHN0cm9uZz5hZGphY2VudCBzd2FwIG9wZXJhdGlvbnM8XC9zdHJvbmc+IGFyZSBnaXZlbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIDxzdHJvbmc+YWRqYWNlbnQgc3dhcCBvcGVyYXRpb25zPFwvc3Ryb25nPiByZXF1aXJlZCBmb3IgdW5pcXVlKCRTXlxccHJpbWUkKSB0byBiZWNvbWUgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktDUEM8XC9jb2RlPjxcL3NwYW4+IG9uIHRoZSBmaXJzdCBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+dW5pcXVlKDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPikgaXMgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktDUEM8XC9jb2RlPjxcL3NwYW4+LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5BcyBzaG93biBiZWxvdyB0aGUgc3RyaW5nIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPiBjYW4gYmUgb2J0YWluZWQgdXNpbmcgYSB0b3RhbCBvZiAkMyQgPHN0cm9uZz5hZGphY2VudCBzd2FwIG9wZXJhdGlvbnM8XC9zdHJvbmc+LCBhbmQgdW5pcXVlKDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LQ1BDPFwvY29kZT48XC9zcGFuPikgaXMgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktDUEM8XC9jb2RlPjxcL3NwYW4+LjxcL3A+XHJcblxyXG48cD48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+Q1A8c3Ryb25nPkNLPFwvc3Ryb25nPjxcL2NvZGU+PFwvc3Bhbj4gJFxccmlnaHRhcnJvdyQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkM8c3Ryb25nPlBLPFwvc3Ryb25nPkM8XC9jb2RlPjxcL3NwYW4+ICRcXHJpZ2h0YXJyb3ckIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT48c3Ryb25nPkNLPFwvc3Ryb25nPlBDPFwvY29kZT48XC9zcGFuPiAkXFxyaWdodGFycm93JCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+S0NQQzxcL2NvZGU+PFwvc3Bhbj48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHA+VGhlIHN0cmluZyA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+S0tDQ1BQQ0M8XC9jb2RlPjxcL3NwYW4+IGNhbiBiZSBvYnRhaW5lZCB1c2luZyBhIHRvdGFsIG9mICQ1JCA8c3Ryb25nPmFkamFjZW50IHN3YXAgb3BlcmF0aW9uczxcL3N0cm9uZz4sIGFuZCB1bmlxdWUoPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktLQ0NQUENDPFwvY29kZT48XC9zcGFuPikgaXMgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPktDUEM8XC9jb2RlPjxcL3NwYW4+LjxcL3A+XHJcbiJ9XQ==