[BOJ/백준][Gold4] 2306 : 유전자 (C++)

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

2306번: 유전자

 

 

[난이도] Gold4
[유형] DP

[풀이]
DP[l][r] : l~r의 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI 유전자의 길이.

k를 l~r-1 증가시키면서 구한 max(DP[l][k]+dp[k+1][r]) 에다

만약 s[i],s[j]가 KOI 유전자일 때, 2+DP[i+1][j-1] 까지 비교해주면 DP[l][r]을 구할 수 있다.

 

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[501][501];
char s[501];
int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = 0;
    if((s[l]=='g'&&s[r]=='c')||(s[l]=='a'&&s[r]=='t')) ret = 2+sol(l+1,r-1);
    for(int i=l;i<r;i++) ret = max(ret,sol(l,i)+sol(i+1,r));
    return ret;
}
int main(){
    scanf("%s",s);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,strlen(s)-1));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2306.cpp