| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 180 | 67 | 61 | 62.887% |
래환이는 하루가 끝날 때마다 자신의 감정을 노트에 적는 것을 즐긴다. 그날의 감정이 전반적으로 기뻤다면 :), 그렇지 않았다면 :(를 적는다.
그렇게 $N$일간 감정을 계속 적다보니 노트에 빈 공간이 없어지기 시작했고, 이전 기록을 압축시켜 정리할 필요성을 느꼈다. 래환이는 연속된 날들의 감정이 동일하면 :) 또는 :( 뒤에 연속된 날의 수를 적기로 했다. 예를 들어 :):):)는 :)3으로 적고, :(:(:):)는 :(2:)2로 적는다. 단, 감정이 하루만 지속되는 경우에는 뒤에 1을 적지 않고 :) 또는 :(만 적는다. 따라서 :):(:(:):)는 :):(2:)2로 적는다.
하지만 감당이 안 될 정도로 많은 기록 때문에 래환이는 $0$개 이상 $K$개 이하의 감정을 반대로 뒤집음으로써 정리된 문자열의 길이를 최소화하려 한다. :)를 뒤집으면 :(가 되고, :(를 뒤집으면 :)가 된다. 이때 래환이는 감정의 전체적인 흐름은 살려두기 위해 뒤집은 이후에도 :)과 :(의 개수가 변하지 않도록 한다.
래환이가 감정 기록을 어떻게 깔끔하게 정리할지 알아맞히는 프로그램을 작성하시오.
첫 번째 줄에 감정 기록을 나타내는 길이 $2N$의 문자열 $S$가 주어진다.
두 번째 줄에 정수 $K$가 주어진다.
감정 기록 $S$를 압축시켜 정리했을 때 만들어지는 문자열의 최소 길이를 출력한다.
:, $S_{2i} \in \{ $ )$,$ ($\}$ $(1 \le i \le N)$| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $K = 0$ |
| 2 | 10 | $K = N$ |
| 3 | 80 | 추가 제약 조건 없음 |
:):):(:):( 2
6
:):):(:):(에서 $3$번째와 $4$번째 감정을 뒤집으면 :):):):(:(가 되어 :)3:(2로 압축할 수 있다.
:(:):):(:( 0
8
:(:):):(:(는 :(:)2:(2로 압축된다.
:):):):):):):):):):):):) 6
4
:):):):):):):):):):):):)는 :)12로 압축되며, 감정을 뒤집더라도 더 짧은 길이로 압축할 수 없다.
$N$의 상한이 $75$인 이유는 KSA는 한 학기에 수업이 총 $15$주 진행되기 때문이다.
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest E번