백준 2306: 유전자(Java)

🎯 목표

• 주어진 DNA 문자열에서 KOI 유전자 조건을 만족하는 최장 유효 부분 문자열의 길이를 구한다.
• KOI 유전자 정의:
  • at, gc는 KOI 유전자.
  • KOI 유전자 X → aXt, gXc도 KOI 유전자.
  • X, Y가 KOI 유전자 → XY도 KOI 유전자.

---

✅ 핵심 아이디어

• DP[i][j]: i~j까지 KOI 유전자 중 최장 길이
• 두 가지 전이 방식:
  1. 경계 조건: (i,j) 가 a,t or g,c로 감싸진다면 → 내부 + 2
  2. 분할 결합: dp[i][j] = max(dp[i][k] + dp[k+1][j])

---

🧠 알고리즘 설계

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

public class Main {
    static int[][] dp;
    static char[] dna;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dna = br.readLine().toCharArray();
        int n = dna.length;

        dp = new int[n][n];

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;

                if (isPair(dna[i], dna[j])) {
                    dp[i][j] = Math.max(dp[i][j], 2 + (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0));
                }

                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }

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

    static boolean isPair(char a, char b) {
        return (a == 'a' && b == 't') || (a == 'g' && b == 'c');
    }
}

---

⏱ 시간복잡도

• O(N³): i, j, k 세중 루프
• N ≤ 500이므로 Java에서도 통과 가능

---

💡 정리

• 이 문제는 전형적인 문자열 DP 문제이며, 분할 정복적 사고와 경계 조건 처리가 핵심
• dp[i][j] = max(경계 포함, 분할) 형태를 잘 이해하자

---