[Algorithm]Baekjoon 2306번 : 유전자

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
 
string s;
int dp[501][501];
 
int dfs(int l, int r)
{
    if (l >= r) return 0;
 
    int& result = dp[l][r];
    if (result != -1) return result;
 
    for (int i = l; i < r; ++i)
    {
        result = max(result, dfs(l, i) + dfs(i + 1, r));
    }
 
    if ((s[l] == 'a' && s[r] == 't') ||
        (s[l] == 'g' && s[r] == 'c'))
    {
        result = max(result, dfs(l + 1, r - 1) + 2);
    }
 
    return result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> s;
 
    memset(dp, -1, sizeof(dp));
 
    cout << dfs(0, s.size() - 1);
}
 

 

간만에 푸는 어려운 dp문제... 원하는 인덱스의 문자는 삭제해도 되기때문에, 삭제하면서 뭔가 완전탐색하는건가?

했는데 그런거 없이 그냥 탐색이 가능하다. 

위 코드를 이해하려면, l, r 인덱스가 어떤식으로 변화하면서 탐색구간이 변경되어지는지 노트에다가 그려보는게 이해하기 쉽다.