[2306번] 유전자

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

이 문제는 DP로 해결 할 수 있는 문제이다.

Top down 방식을 이용하여 재귀로 풀어 나갈 수 있으며 처음과 마지막이 a ~ t 혹은 g ~ c인지 확인하고

맞으면 처음 + 1, 마지막 - 1을 인자로 보내고, 그다음 부터는 for문을 이용하여 한칸씩 뛰어서 보는 과정을 이용하면 된다.

말로 설명을 하기보다 코드를 보면 이해하기가 더 쉬우니 코드를 통해 문제를 해결해보자.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <memory.h>   using namespace std; string str; int dp[502][502];   int go(int s, int e) {     int ret = dp[s][e];       if (ret != -1)         return ret;       ret = 0;       if ((str[s] == 'a' && str[e] == 't') || (str[s] == 'g' && str[e] == 'c'))         ret = go(s + 1, e - 1) + 2;       for (int i = s; i < e; i++)         ret = max(ret, go(s, i) + go(i + 1, e));       return dp[s][e] = ret; }   int main() {     cin >> str;     int len = str.size();       memset(dp, -1, sizeof(dp));       cout << go(0, len - 1);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus