BOJ 2806 - DNA 발견 [Java]

 

 

문제

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

0, 1로만 이루어진 길이 $N$인 1-based index 수열 $S$에, $1 \le i \le N$을 골라서 아래 두 가지 연산을 할 수 있다.

1. $S[i] = S[i] \oplus 1$

2. $S[1] = S[1] \oplus 1, \cdots, S[i] = S[i] \oplus 1$

$ \oplus $는 exclusive or를 의미한다.

모든 원소를 $0$으로 만드는 데 필요한 최소 연산 횟수를 구하는 문제이다.

풀이

$1$인 원소를 $0$으로 만드는 방법에는 아래 것들이 존재한다.

1. 모든 원소 $1$에 대해, 1번 연산 수행하기

2. 특정 구간 $[l,r]$의 원소가 모두 $1$일 때, 2번 연산을 각각 $i = l-1, i=r$로 잡고 수행하기

3. 모든 원소 $0$을 $1$로 만들고 2번 연산을 전체에 적용하기

 

모두 $1$로 만드는 경우와 모두 $0$으로 만드는 경우에 대한 DP식을 각각 정의하고, 위의 관계를 적용시켜 풀면 된다.

 

import java.util.*;
import java.io.*;

public class Main {
    static StringTokenizer st;
    static int nextInt() { return Integer.parseInt(st.nextToken()); }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        String S = br.readLine();
        int[] dp1 = new int[N];
        int[] dp2 = new int[N];
        int last_a = -1, last_b = -1;

        if(S.charAt(0)=='A') {
            dp2[0] = 1;
            last_a = 0;
        }
        else {
            dp1[0] = 1;
            last_b = 0;
        }

        for(int i=1;i<N;i++) {
            if(S.charAt(i)=='A') {
                dp1[i] = dp1[i-1];
                dp2[i] = dp2[i-1] + 1;
                if(last_b != -1) dp2[i] = Math.min(dp2[i], dp2[last_b]+2);
                last_a = i;
            }
            else {
                dp2[i] = dp2[i-1];
                dp1[i] = dp1[i-1] + 1;
                if(last_a != -1) dp1[i] = Math.min(dp1[i], dp1[last_a]+2);
                last_b = i;
            }
            dp1[i] = Math.min(dp1[i], dp2[i]+1);
            dp2[i] = Math.min(dp2[i], dp1[i]+1);
        }
        bw.write(dp1[N-1]+"\n");


        bw.close();
    }

}