[백준 2806] DNA 발견 (JAVA)

문제

---

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

풀이

---

DP로 해결하는 문제입니다.
첫번째 문자부터 확인하여 전부 A로 바꾼 경우, 전부 B로 바꾼 경우로 진행하면 됩니다.

1) 첫 문자는 A이므로 A로 통일하는 경우는 변경 횟수가 0, B로 통일하는 경우는 1입니다.

-	A	B	B	A
A	0
B	1

2) 두번째 문자는 B이므로 B를 먼저 채우고 A[i-1]+1 과 B[i]+1을 비교하여 더 작은 수를 넣습니다.

-	A	B	B	A
A	0	1
B	1	1

3) 세번째 문자는 B이므로 2번과 같습니다.

-	A	B	B	A
A	0	1	2
B	1	1	1

4) 네번째 문자는 A입니다.

-	A	B	B	A
A	0	1	2	2
B	1	1	1	2

5) B로 통일한 경우 A로 다시 바꿔야하기 때문에 A[N-1]과 B[N-1]+1 중에 최솟값을 출력합니다.

코드

---

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        String dna = br.readLine();
        int[][] dp = new int[2][N];

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

        for (int i = 1; i < N; i++) {
            char c = dna.charAt(i);

            if (c == 'A') {
                dp[0][i] = dp[0][i-1];
                dp[1][i] = Math.min(dp[1][i-1] + 1, dp[0][i] + 1);
            } else {
                dp[1][i] = dp[1][i-1];
                dp[0][i] = Math.min(dp[0][i-1] + 1, dp[1][i] + 1);
            }
        }

        int ans = Math.min(dp[0][N-1], dp[1][N-1] + 1);
        System.out.println(ans);
        br.close();
    }
}