| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 641 | 128 | 114 | 23.950% |
0ドル$과 1ドル$로 이루어진 길이 $n$의 이진 문자열 $a_1a_2...a_n$이 주어진다. 여러분은 비용 1ドル$로 하나의 문자를 다른 문자로 바꿀 수 있다.
좋은 이진 문자열은 다음을 만족하는 문자열이다.
주어진 문자열을 좋은 이진 문자열로 만드는 데 필요한 최소 비용을 구하시오.
첫째 줄에는 테스트케이스의 개수 $T$가 주어진다. (1ドル \leq T \leq 10^3$)
각 테스트케이스는 다음과 같은 구성을 가진다.
첫째 줄에는 이진 문자열의 길이 $n$이 주어진다. (1ドル \leq n \leq 10^6$)
다음 줄에는 0ドル$과 1ドル$로 이루어진 길이 $n$의 문자열이 주어진다.
모든 테스트케이스에 대해서 $n$의 합이 10ドル^6$ 이하임이 보장된다.
각 테스트 케이스에 대해서 주어진 문자열을 좋은 이진 문자열로 만들 수 없다면 $-1$을 출력한다. 좋은 이진 문자열로 만들 수 있다면 좋은 이진 문자열로 만들기 위한 최소 비용을 출력한다.
3 6 100100 5 10010 1 0
1 0 -1
첫 번째 테스트케이스의 경우, 5ドル$번째 문자를 1ドル$로 바꾸면 문자열이 100110ドル$이 된다.
[1ドル,ドル 5ドル$]는 1ドル$을 포함하며 이는 1ドル$을 포함하는 구간 중 최소 길이를 가지는 구간이다.
[2ドル,ドル 6ドル$]는 0ドル$을 포함하며 이는 0ドル$을 포함하는 구간 중 최소 길이를 가지는 구간이다.
두 구간 모두 길이가 4ドル$이기 때문에 새로 만든 문자열은 좋은 이진 문자열이다.
비용 0ドル$으로는 좋은 문자열을 만들 수 없다.
두 번째 테스트케이스의 경우 문자열이 이미 좋은 문자열이기 때문에 답은 0ドル$이다.
세 번째 테스트케이스의 경우 길이 1ドル$의 문자열은 1ドル$과 0ドル$을 둘 다 포함할 수 없기 때문에 주어진 문자열을 좋은 문자열로 만들 수 없다.
University > 신촌지역 대학생 프로그래밍 대회 동아리 연합 > 2023 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2023 Winter) M번