[BAE/<JOON> 문제풀이] 2306. 유전자

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

2306번: 유전자

서론

DP 감 다죽었다. 이걸 3일 동안 코너케이스 찾음;;

풀이

인덱스 i, j 가 유전자 쌍을 이룰 때 i+1 ~ j-1 사이의 가장 긴 유전자 일치 길이에 +2를 해서 저장하면 된다.

추가적으로 독립적인 유전자 쌍 n개가 포함된 경우 길이를 모두 더해줘야 한다. 유전자 쌍의 최소 길이는 2 이므로 

추가 인덱스 l ( l : j+1 ~ k-2 ) 을 기준으로 2개의 구간으로 나눠 두 인덱스의 합 중 최댓값을 저장하여 구할 수 있다.

만약 i, j 의 유전자가 서로 일치하지 않을 경우 i+1,j 구간과 i, j-1 구간 중 더 긴 인덱스를 계승하기만 하면 된다.

 

아래는 맞왜틀하면서 만들었던 테스트 케이스 목록이다.

agatcatt 답 : 8
agct 답 : 4
agtc 답 : 2
aagctt 답 : 6

agcgct 답 : 6

aggcct  답 : 6

aagctt 답 : 6
aagtct 답 : 6
tttaattttt 답 : 4
aatttt 답 : 4

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
struct cp {
    int mx, c, p = -1;
};
int main()
{
    string s; cin >> s; int n = s.size(); vector<int> arr(n + 1); vector<cp> srr(n + 1);
    for (int i = 1; i <= n; i++) {
        arr[i] = (s[i - 1] == 'a' ? 1 : s[i - 1] == 't' ? 2 : s[i - 1] == 'g' ? 3 : s[i - 1] == 'c' ? 4 : -1);
    }    
    vector<vector<int>> dp2(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n - i; j++) {
            int k = j + i;
            if ((arr[j] == 1 && arr[k] == 2) || (arr[j] == 3 && arr[k] == 4)) {
                int s1 = dp2[j + 1][k - 1] + 2;
                dp2[j][k] = dp2[j][k] > s1 ? dp2[j][k] : s1;
                for (int l = j + 1; l < k - 1; l++) {
                    int s1 = dp2[j][l] + dp2[l + 1][k];
                    dp2[j][k] = dp2[j][k] > s1 ? dp2[j][k] : s1;
                }
            }
            else {
                dp2[j][k] = dp2[j + 1][k] > dp2[j][k - 1] ? dp2[j + 1][k] : dp2[j][k - 1];
                for (int l = j + 1; l < k - 1; l++) {
                    int s1 = dp2[j][l] + dp2[l + 1][k];
                    dp2[j][k] = dp2[j][k] > s1 ? dp2[j][k] : s1;
                }
            }
        }
    }    
    cout << dp2[1][n];   
    return 0;
}