35297번 - KSA 문자열 3 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 274 | 118 | 108 | 53.465% |
문제
KSAAC 운영진은 모두 KSA를 사랑하기 때문에 다음 조건을 만족하는 문자열을 좋아한다.
문자열의 길이를 $N$이라고 할 때, $1 \leq i \leq N$인 모든 $i$에 대하여
- $i$를 $3$으로 나눈 나머지가 $1$이면 $i$번째 문자는
K이다. - $i$를 $3$으로 나눈 나머지가 $2$이면 $i$번째 문자는
S이다. - $i$를 $3$으로 나눈 나머지가 $0$이면 $i$번째 문자는
A이다.
문자열에는 다음 시행을 $0$회 이상 할 수 있으며 매회 둘 중 하나를 선택하여 시행할 수 있다.
- 존재하는 문자들 중 인접한 문자 2개를 제거한다.
- 문자열의 맨 앞에 동일한 문자를 2개 추가한다.
주어진 문자열 $X$에 적절한 시행을 하여 $X$를 $X$와 길이가 같으면서 KSAAC 운영진이 좋아하는 문자열로 바꾸려고 한다. 이때 필요한 시행의 최소 횟수를 구하여라.
입력
첫 번째 줄에 문자열 $X$가 주어진다.
출력
문자열 $X$를 $X$와 길이가 같으면서 KSAAC 운영진이 좋아하는 문자열로 바꾸기 위한 최소 시행 횟수를 출력한다.
주어진 시행을 유한 번 하는 것으로 문자열 $X$를 $X$와 길이가 같으면서 KSAAC 운영진이 좋아하는 문자열로 바꿀 수 있음이 보장된다.
제한
- $1 \le |X| \le 5 \times 10^5$
- $X_i \in \{$
K$,$S$,$A$\}$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $X$의 모든 문자가 동일 |
| 2 | 80 | 추가 제약 조건 없음 |
예제 입력 1
KSKA
예제 출력 1
8
주어진 문자열을 KSAK로 만드는 것이 목표이다.
KK, SS, AA, KK를 추가하면 문자열이 KKSSAAKKKSKA가 되는데 여기서 $2$, $6$, $9$, $11$번째 문자와 그 오른쪽에 위치한 문자를 삭제하면 KSAK가 된다.
예제 입력 2
KKK
예제 출력 2
6
주어진 문자열을 KSA로 만드는 것이 목표이다.
KK, SS, AA를 추가하면 문자열이 KKSSAAKKK가 되는데 여기서 $2$, $6$, $8$번째 문자와 그 오른쪽에 위치한 문자를 삭제하면 KSA가 된다.
출처
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest C번
- 문제를 만든 사람: sooahn07
- 문제를 검수한 사람: bennyk0406, eric00513, flakepowders, hjroh0315, mythofys, number0316, parkky, pkearth, raehwan0418, sadtreap, utilforever, wizardrabbit
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.