[BOJ 2806] DNA 발견

아래와 같이 정의하자.

$C_i$: $i$번째 문자 $(A|B)$

$f(i, A)$: $C_i$까지 봤을 때, 모두 $A$로 만드는 최소 비용

$f(i, B)$: $C_i$까지 봤을 때, 모두 $B$로 만드는 최소 비용

 

$C_i=A$라면,

• $f(i, A)=\min (f(i-1, A), f(i-1, B) + 1)$
  • $AA\dots AA + A$라면 그대로 유지
  • $BB\dots BB + A$라면 $BB\dots BB$를 모두 $A$로 변경

• $f(i, B)=\min (f(i-1, A), f(i-1, B)) + 1$
  • $AA\dots AA + A$라면 전체를 $B$로 변경
  • $BB\dots BB + A$라면 $A$를 $B$로 변경

$C_i=B$라면, 

• $f(i, A)=\min (f(i-1, A), f(i-1, B)) + 1$
  • $AA\dots AA + B$라면 $B$를 $A$로 변경
  • $BB\dots BB + B$라면 전체를 $A$로 변경
• $f(i, B)=\min (f(i-1, A) + 1, f(i-1, B))$
  • $AA\dots AA + B$라면 $AA\dots AA$를 모두 $B$로 변경
  • $BB\dots BB + B$라면 그대로 유지

이와 같이 진행할 수 있다. 답은 $\min (f(N, A), f(N, B) + 1)$이 된다.

int N, dp[MAXN][2];
char dna[MAXN];

int main(void) {
    fastio;
    cin >> N >> dna;

    if (dna[0] == 'A') {
        dp[0][0] = 0;
        dp[0][1] = 1;
    }
    else {
        dp[0][0] = 1;
        dp[0][1] = 0;
    }

    for (int i = 1; i < N; i++) {
        if (dna[i] == 'A') {
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1);
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
        }
        else {
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
            dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1]);
        }
    }
    cout << min(dp[N - 1][0], dp[N - 1][1] + 1);
    return 0;
}