217번째 문제 - 2306 유전자

간만에 포스팅. 바빠서 문제 풀이를 많이 하지는 못했고 또 푼 문제 중에서도 그닥 포스팅 하고 싶은 문제가 없었다.

이 문제는 간단한 dp 문제지만 중간에 삽질로 오래 걸려서 포스팅한다.

점화식은 다음과 같다.

1. 어떤 X가 KOI 유전자라면, aXt와 gXc도 KOI 유전자이다.
   
   d[l][r] = d[l+1][r-1] + 2 l, r 문자가 at 혹은 gc 일때 : d[l][r] = max(d[l][r] , d[l+1][r-1] + 2)
   
   
   
2. 어떤 X와 Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다.
   
   for(int i=l+1; i<r; i++) d[l][r] = max(d[l][r], d[l][i]+d[i+1][r]);
   
   
   
3. KOI 유전자는 DNA 서열 중에서 부분 서열로 구성되어 있다. 
   
   d[l][r] =  max(d[l][r], d[l][r-1]);
   d[l][r] = max(d[l][r], d[l+1][r]);

코드

#include <iostream>

#include <string>

#include <memory.h>

#include <algorithm>

using namespace std;

int d[501][501];

string t;

bool isKOI(char l, char r)

{

if(l=='a' && r =='t') return true;

else if(l =='g' && r =='c') return true;

else return false;

}

void dp(int l, int r)

{

int &ans = d[l][r];

if(ans!=-1) return;

if(l>=r)

{

ans = 0;

}

else if(r-l == 1) 

{

if( isKOI(t[l],t[r])) ans = 2;

else ans =  0;

}

else

{

int res=0;

dp(l+1,r-1);

if( isKOI(t[l], t[r]) )

{

res = max(res, d[l+1][r-1]+2);

}

dp(l+1,r); res = max(res, d[l+1][r]);

dp(l,r-1);

res = max(res, d[l][r-1]);

for(int i=l+1; i<r; i++)

{

dp(l,i);

dp(i+1,r);

res = max(res, d[l][i]+d[i+1][r]);

}

ans = res;

}

}

void solve()

{

memset(d,-1,sizeof(d));

cin>>t;

dp(0,t.length()-1);

cout<<d[0][t.length()-1];

}

int main()

{

solve();

}