[BaekJoon] 2306 유전자 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static char[] dna;

    static void input() {
        Reader scanner = new Reader();
        dna = scanner.nextLine().toCharArray();
    }

    /*
     * DP를 이용하여 해결한다
     *  1. KOI 유전자의 조건으로 어떤 X가 KOI 유전자라면 aXt 또는 gXc도 KOI 유전자라고 하였다
     *      - 길이가 1인 경우부터 주어진 DNA 서열의 길이까지 한 위치를 기준으로 해당 길이만큼의 부분 문자열 중
     *        양쪽 끝 문자가 각각 at 혹은 gc라면 그 사이에 있는 문자열에서 최대 KOI 유전자 길이에 2를 더해준다
     *  2. KOI 유전자의 조건으로 어떤 X와 Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자라고 하였다
     *      - 길이가 1인 경우부터 주어진 DNA 서열의 길이까지 한 위치를 기준으로 해당 길이만큼의 부분 문자열 중
     *        중간 한 부분을 잡고 시작부터 중간까지, 중간 바로 다음부터 끝까지 2개의 문자열에서
     *        각각 최대 KOI 유전자 길이를 구하고 그 두 길이를 더하면 전체 부분 문자열에서의 최대 KOI 유전자 길이가 된다
     *
     * 위 2가지 방법으로 각각 최대 KOI 유전자 길이를 구했다면 둘 중 더 긴 것을 각 부분 문자열에서의 최대 KOI 유전자 길이로 정한다
     *
     * 이를 통해 주어진 DNA 서열의 최대 KOI 유전자 길이를 구한다
     */
    static void solution() {
        int[][] dp = new int[dna.length][dna.length];
        for (int length = 1; length < dna.length; length++) {
            for (int startIdx = 0; startIdx + length < dna.length; startIdx++) {
                int endIdx = startIdx + length;

                if (isKOI(startIdx, endIdx)) {
                    dp[startIdx][endIdx] = dp[startIdx + 1][endIdx - 1] + 2;
                }

                for (int midIdx = startIdx; midIdx < endIdx; midIdx++) {
                    dp[startIdx][endIdx] = Math.max(dp[startIdx][endIdx],
                            dp[startIdx][midIdx] + dp[midIdx + 1][endIdx]);
                }
            }
        }

        System.out.println(dp[0][dna.length - 1]);
    }

    static boolean isKOI(int startIdx, int endIdx) {
        return (dna[startIdx] == 'a' && dna[endIdx] == 't') || (dna[startIdx] == 'g' && dna[endIdx] == 'c');
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}