[白俊2806]DNA発見(JAVA)

質問する

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

に答える

DPによって解決される問題.
最初の文字から確認してすべてAに変換すると、すべてBに変換されます.
1)最初の文字がAであるため、Aに統一した場合、変更回数が0、Bに統一した場合は1となる.
-ABBAA0B1
2)2番目の文字がBであるため、まずBを埋め、A[i-1]+1とB[i]+1を比較してより小さい数字を追加する.
-ABBAA01B11
3)3番目の文字はBで、2番目の文字のようです.
-ABBAA012B111
4)4番目の文字はAです.
-ABBAA0122B1112
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();
    }
}