[백준] 2306: 유전자(feat. DP 엣지케이스 주의)

 

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

2306번: 유전자

그동안 접했던 다이나믹 프로그래밍보다 훨씬 어려운 문제였다...

처음에는 단순한 문제로만 생각했어서 단순하게 풀려고 했는데 자꾸 예상치 못했던 케이스들이 등장했다.

 

부분 서열로 구성할 수 있고, 다양한 조건이 있지만 사실 {a,t}, {g,c} 를 매치하고 최대 부분 수열을 만들면  된다는 것으로 귀결된다.

여기까지는 좋았다.

하지만 그 다음부터 조건을 잘못 설정하여 문제를 제대로 풀지 못했다.

가장 최근에 등장한 a와 g를 각각 t와 c 매치하였다. 하지만 이는 잘못된 생각이었다.

 

1. 

가장 최근 알파벳을 매치하는 것은 최선의 답이 아니었다.

예를 들어 gagtc에서 가운데 g를 제외해 매치하는 작업을 수행해야 최대 길이가 4가 된다.

 

2.

놓쳤던 엣지 케이스가 있다.

이전까지는 매치가 반드시 nested되는 것을 전제하였으나 그러면 안됐다.

만약 매치가 엇갈리는 경우도 고려해야 한다. 엣지 케이스로 agtc가 있다.

 

이는 부분수열의 시작점과 도착점에 따라 최대 KOI 문자열 길이가 달라지기 때문에 시작점과 도착점에 따라  2차원 다이나믹 프로그래밍을 시행해야 한다.

$dp[i][j]$ : 부분 문자열 s[i,j] 사이의 최대 KOI 문자열 길이

 

 

그리고 앞뒤로 KOI 문자열에 해당되는지를 확인해야하기 때문에 단순히 linear하게 탐색을 할 수 없다.

이번에는 간격을 확장해나가며 탐색을 한다.

 

기본적인 점화식

k를 기준으로 두 부분으로 나누어서 수열 내 부분 수열을 합쳐 최대 길이를 구할 수 있다.

$dp[i][j] = max_{k = i}^{k=j - 1}{(dp[i][k] + dp[k + 1][j])}$

 

그리고 만약 {i, j}로 {a,t}나 {g,c}를 발견하면 [i + 1, j - 1] 즉 내부의 문자수열보다 길이를 2 늘려서 dp[i][j]로 저장한다.

만약 to[s[i]]  == s[i]인 경우

$dp[i][j] = dp[i + 1][j - 1] + 2$

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[500][500];
char to['z'];
int main()
{
    string dna;
    int answer = 0;
    to['a'] = 't';
    to['g'] = 'c';
    cin >> dna;
    int n = dna.length();
    // l: i와 j의 간격
    // [i, j]
    for(int l = 1;l < n;l++) {
      for(int i = 0;i + l< n;i++) {
        int j =  i + l;
        if((dna[i] == 'a' || dna[i] == 'g') && to[dna[i]] == dna[j]) {
          dp[i][j] = dp[i + 1] [j - 1] + 2;
        }

        for(int k = i;k < j;k++) {
          dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
        }
      }
    }
    
    cout << dp[0][n - 1] << '\n';
}