BAEKJOON 8913번: 문자열 뽑기

https://www.acmicpc.net/problem/8913

8913번: 문자열 뽑기

풀이

문자열의 길이가 최대 25정도로 매우 작기 때문에 모든 경우의 수를 다 확인할 수 있다. 문자열을 bit로 표현하여 뽑아낼 수 있는 부분을 차례대로 뽑아내면서 한번이라도 가능한 경우가 나오면 탐색을 중단하고 1을 출력한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
char S[30];
bool f(int bit,int len){
    if(len==0)return true;else if(len==1)return false;
    vector<bool>A(len+1,0);
    vector<int>P(len+1,0);
    P[0]=1;
    for(int i=0;i<len;i++)A[i]=(1<<i)&bit;
    for(int i=1;i<len;i++){
        if(A[i]==A[i-1])P[i]=P[i-1]+1;else P[i]=1;
    }
    bool ret=false;int i=len-1;
    while(i>0){
        int s,e;
        if(P[i]>1){
            s=i-P[i]+1,e=i;
            i-=P[i];
            int tmp=0;
            for(int j=0;j<s;j++)if(A[j])tmp+=1<<j;
            for(int j=e+1;j<len;j++)if(A[j])tmp+=1<<(j-e+s-1);
            if(f(tmp,len-e+s-1))ret=true;
            if(ret)break;
        }else i--;
    }
    return ret;
}
int main(){
    int T,N,bit;
    scanf("%d",&T);
    while(T--){
        scanf("%s",S);
        N=strlen(S);bit=0;
        for(int i=0;i<N;i++){
            if(S[i]=='b')bit+=1<<i;
        }
        printf("%d\n",f(bit,N));
    }
    return 0;
}