백준 2806 자바 - DNA 발견 (BOJ 2806 JAVA)

문제 : boj2806

 

 

1.

  문자를 하나씩 보면서 전부 A, 혹은 B로 변경해 나간다고 생각해보자.

그렇다면 8가지 경우가 나온다.

 

case1. 현재 문자는 A, 이전까지 전부 A 였음, 전부 A로 유지할 것임

  -> 이전 상태에 그냥 A를 붙이면 된다. (돌연변이 +0)

 

case2. 현재 문자는 A, 이전까지 전부 A 였음, 전부 B로 유지할 것임

  -> 이전 상태에 그냥 A를 붙인 후, 전체를 B로 변경한다. (돌연변이 +1)

 

case3. 현재 문자는 A, 이전까지 전부 B 였음, 전부 A로 유지할 것임

  -> 이전 상태 전체를 A로 변경하고 A를 붙인다. (돌연변이 +1)

 

case4. 현재 문자는 A, 이전까지 전부 B 였음, 전부 B로 유지할 것임

  -> 현재 문자를 B로 변경해서 붙인다. (돌연변이 +1)

 

case5~8 -> 현재 문자가 B인 경우에 case 1~4를 대입해보면 된다.

 

 

2.

  그럼 이걸 dp로 표현해보자. dp[x][y]는 x 인덱스 문자열까지 봤을 때 A(y=0)와 B(y=1)로 유지하려할 때 필요한 돌연변이의 최소 횟수이다.

그럼 '1'에서 설명했던 case에 맞춰 점화식을 세워보면

 

[ 현재 문자가 'A'일 때 ]

A로 유지하려면 dp[i][0] = min( dp[i-1][0], dp[i-1][1]+1 )

-> 이전에 A로 유지되던거에 A를 붙이거나(돌연변이+0), 이전에 B로 유지되던거를 전부 A로 변경하고 A를 붙임(돌연변이+1)

 

B로 유지하려면 dp[i][1] = min( dp[i-1][0]+1, dp[i-1][1]+1 )

-> 이전에 A로 유지되던거에 A를 붙인 후 전부 B로 변경(돌연변이+1) 하거나, 이전에 B로 유지되던거에 A를 B로 변경하여 붙임(돌연변이+1)

 

[ 현재 문자가 'B'일 때 ]

A로 유지하려면 dp[i][0] = min( dp[i-1][0]+1, dp[i-1][1]+1 )

-> 이전에 B로 유지되던거에 B를 붙인 후 전부 A로 변경(돌연변이+1) 하거나, 이전에 A로 유지되던거에 B를 A로 변경하여 붙임(돌연변이+1)

 

B로 유지하려면 dp[i][1] = min( dp[i-1][0], dp[i-1][1]+1 )

-> 이전에 B로 유지되던거에 B를 붙이거나(돌연변이+0), 이전에 A로 유지되던거를 전부 B로 변경하고 B를 붙임(돌연변이+1)

 

와 같고, 이미지로 나타내보면 아래와 같다.

 

최종적으로 dp[n-1][0]과 dp[n-1][1]+1 (B로 유지된것이니 전체를 A로 변경해야되서 +1) 중 작은 값을 출력하면 된다. 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final int A = 0;
    private static final int B = 1;

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();

        int[][] dp = new int[n][2];
        dp[0][B] = 1-(dp[0][A] = s.charAt(0)=='A'?0:1);
        for (int i = 1; i < n; i++) {
            boolean isA = s.charAt(i) == 'A';
            dp[i][isA?A:B] = Math.min(dp[i-1][isA?A:B], dp[i-1][isA?B:A]+1);
            dp[i][isA?B:A] = Math.min(dp[i-1][isA?A:B], dp[i-1][isA?B:A])+1;
        }
        System.out.println(Math.min(dp[n-1][A], dp[n-1][B]+1));
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}