[BOJ 10258] 스위치 배열
View as PDF
Submit solution
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
Points:
4
Time limit:
1.0s
Memory limit:
256M
Problem types
Allowed languages
새로운 잠금 장치가 개발되었다.
이 장치는 열리거나 닫힌 상태를 갖는 여러 스위치(s1, s2 ,.., si-1, si)들로 이루어져 있으며, 각각의 스위치는 0 또는 1의 상태를 갖는다. 따라서, 각 장치는 0과 1로 이루어진 스위치 배열로 나타낼 수 있다.
다음 표는 8개의 스위치를 가진 스위치 배열의 예제이다.
| switch | s1 | s2 | s3 | s4 | s5 | s6 | s7 | s8 |
|---|---|---|---|---|---|---|---|---|
| state | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
N개의 스위치를 가진 배열의 각 스위치를 작동시키는 규칙은 다음과 같다.
- 규칙 1) SN은 아무 때나 토글하여 상태를 바꿀 수 있다.
- 규칙 2) Si+1 = 1이며 Si+2, Si+3, ..., SN-1, SN은 모두 0일 때, Si를 토글하여 상태를 바꿀 수 있다. 이 규칙은 스위치 Si+2, Si+3, ..., SN-1, SN가 없을 때도 적용된다. 예를 들어, SN-1은 SN이 1이기만 하면 토글할 수 있다.
- 규칙 3) 한 번에 하나의 스위치만 토글할 수 있다.
모든 스위치의 상태가 0일 때 이 장치는 열린다.
위의 규칙에 따라 배열을 모두 0으로 바꾸는 최소 토글 횟수를 구하는 것이 당신의 과제이다.
아래의 표는 배열 '1111' 을 '0000' 으로 바꾸는 최소 횟수의 연산을 나타낸 것이다. '1111' 의 경우, 최소 10번의 연산으로 배열을 '0000' 으로 만들 수 있다.
| operation | s1 | s2 | s3 | s4 |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 2 | 1 | 1 | 0 | 0 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 0 | 1 | 0 | 1 |
| 5 | 0 | 1 | 1 | 1 |
| 6 | 0 | 1 | 1 | 0 |
| 7 | 0 | 0 | 1 | 0 |
| 8 | 0 | 0 | 1 | 1 |
| 9 | 0 | 0 | 0 | 1 |
| 10 | 0 | 0 | 0 | 0 |
입력 형식
입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스마다 비트스트링 B가 한 줄에 주어지며, B의 첫 비트가 S1, 마지막 비트가 SN이다.
B의 길이는 2 ≤ |B| ≤ 31 을 만족한다.
출력 형식
각 테스트 케이스마다 한 줄에 모든 스위치를 0으로 만들기 위한 최소의 연산 횟수를 출력한다.
예제 입력
5
1111
11111
1010101010
000
000000010예제 출력
10
21
819
0
3
Comments