백준 15910 바나나나빠나나 (C++)

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

15910번: 바나나나빠나나

생소한 dfa때문에 풀기 어려웠던 문제였습니다. dfa를 통해 문자열에서 패턴을 찾을 수 있습니다. 문자열에서 어떤 위치를 상태로 가정하고 이에 따라 다음은 패턴에 따라 어디로 전이되야하는지(어떤 문자가 나와야하는지)를 알 수 있습니다.

우리는 이를 문제에 어떻게 적용할 수 있을까요. 원래대로 라면 dfa로 패턴을 매칭할때 나와야 하는 문자가 나오지 않을경우 초기상태부터 시작하지만 문제에 적용하면 우리는 문자가 나오지 않을경우에 문자를 바꿀 수 있습니다. 

이를 dp를 적용해서 이전문자의 상태에서 현재 문자의 어떤 상태로 전이되었다 가정했을때 이전 문자까지의 바꾼 횟수의 최소값을 사용할 수 있습니다. 즉

(현재 문자에서의 어떤 상태 i 에서 바꾼 횟수 최소값) = min(이전문자에서 i로 갈 수 있는 상태들의 바꾼 횟수 최소값) 이 됩니다.  또한 현재문자와 어떤 상태 i에서의 기대값이 틀리다면 +1해주면 됩니다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<bitset>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int dp[100001][7];
int main(){
    fast_io();
    string input;
    cin>>input;
    int k=(int)input.size();
    for(int x=0;x<k;x++){
        for(int y=0;y<7;y++) dp[x][y]=1e9;
    }
    dp[0][0]=0;
    for(int x=1;x<=k;x++){
        dp[x][1]=min(dp[x-1][0]+(input[x-1]!='B'),dp[x-1][1]+(input[x-1]!='B'));
        dp[x][1]=min(dp[x][1],dp[x-1][6]+(input[x-1]!='B'));
        dp[x][2]=dp[x-1][1]+(input[x-1]!='A');
        dp[x][3]=dp[x-1][2]+(input[x-1]!='N');
        dp[x][4]=dp[x-1][3]+(input[x-1]!='A');
        dp[x][5]=min(dp[x-1][4]+(input[x-1]!='N'),dp[x-1][6]+(input[x-1]!='N'));
        dp[x][6]=dp[x-1][5]+(input[x-1]!='A');
    }
    cout<<dp[k][6];
}