J. Switch Array

비트 문자열이 있을 때, 각 자리의 비트를 switch 할 수 있는 규칙이 2가지 있다. 이 두 가지 규칙을 통하여 주어진 비트 문자열의 모든 자리를 0으로 만드는 최소 회수를 구하는 문제다.

문제를 뒤집어 모든 자리가 0으로 되어 있는 비트 문자열에서 입력으로 주어진 비트 문자열을 만들기 위한 최소 회수를 구하는 문제로 바꾸자. 그러면 이제 왼쪽에 있는 1비트 부터 차례대로 만드는 것이 회수를 최소화 한다. 

아래와 같은 값을 미리 계산해둔다.

D[i] = 비트문자열의 모든 자리가 0이라고 할 때, 오른쪽에서 i번째 비트를 1로 만드는 최소 회수

D[i] = D[i-1]*2+1, D[1] = 1

D[i] = 2^i - 1

가장 왼쪽에 있는 1비트를 만들기 위한 최소 회수는 몇 일까? 그 비트의 위치를 왼쪽에서 i 번째라고 한다면, D[N-i+1] 번이 된다. 하지만 그보다 오른쪽에 있는 1비트를 만들기 위해 i+1 번째 비트를 1로 남기자. 그러면 D[N-i]+1번의 연산 만에 0...0110...0 꼴의 비트문자열을 만들 수 있다. 이후 D[N-i-1]+1번의 연산으로 0...01010...0 꼴의 비트문자열을 만들 수 있다. 이제 어느 정도 규칙이 눈에 보인다. 이 과정을 다음 1 비트가 나올 때 까지 반복하면 된다. 그러면 왼쪽의 두 1비트를 만들었다. 이제 다시 처음으로 돌아가 왼쪽에서 세 번째, 네 번째 1비트를 만들 수 있다. 이처럼 왼쪽에서부터 1비트 두 개씩 만들어간다. 이와 같은 과정으로 만드는 것이 최소 회수임을 보일 수 있다.

#include <stdio.h> #include <string.h> typedef long long lld; int T,N; lld D[32]={0,1}; char A[32]; int main() { int i,j,k; for (i=2;i<32;i++) D[i] = D[i-1]+1+D[i-1]; for (scanf("%d",&T);T--;){ scanf("%s",A+1); N = strlen(A+1); for (i=1;i<=N;i++) A[i] -= '0'; lld ans = 0; for (i=1;;){ for (;i<=N;i++) if (A[i]){ break; } if (i > N) break; A[i] = 0; ans += D[N-i]+1; for (i++;i<=N;i++){ if (A[i]) break; ans += D[N-i]+1; } A[i++] = 0; } printf("%lld\n",ans); } }