[BOJ] 백준 2306 - 유전자

문제 링크

www.acmicpc.net/problem/2306

2306번: 유전자

 

풀이

DP 문제입니다. 상태를 다음과 같이 정의합시다.

$D[i][j]$: 부분 문자열 $s[i, j]$의 최대 KOI 유전자 길이

 

1) 우선 간단하게 $i$이상 $j$미만의 모든 $k$에 대해,

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

이런 방식으로 i ~ j를 가능한 모든 두 구간으로 나누어보면 최댓값을 구할 수 있습니다.

 

2) 만약 $s[i] == s[j]$인 경우

$$D[i][j] = max(D[i][j], 2 + D[i+1][j-1])$$

까지 고려해주면 됩니다.

 

 

정답 코드

#include <bits/stdc++.h>
 
using namespace std;
 
string s;
int n;
char to['z'];
int d[555][555];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    to['a'] = 't';
    to['g'] = 'c';
    cin >> s;
    n = s.size();
    for (int l = 1; l < n; l++) {
        for (int i = 0; i + l< n; i++) {
            int j = i + l;
            if ((s[i] == 'a' || s[i] == 'g') && s[j] == to[s[i]]) {
                d[i][j] = d[i + 1][j - 1] + 2;
            }
            for (int k = i; k < j; k++) {
                d[i][j] = max(d[i][j], d[i][k] + d[k + 1][j]);
            }
        }
    }
    cout << d[0][n - 1];
}