[백준] 2306번 유전자

문제 위치 : https://www.acmicpc.net/problem/2306

---

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다.

 

-> KOI 유전자가 될 수 있는 최대 길이를 문자열의 처음, 끝부터 분할해나가면서 확인한다.

 

(2) DP 배열 정의

 

-> DP[s][e] : start 부터 end 까지 KOI의 최대 길이

 

(3) 후기

 

1. 문자열의 특정 패턴, 조건 등으로 길이를 구할 때 사용할 수 있다.

 

2. Source Code

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#define MAX 500
#define START0 'a'
#define END0 't'
#define START1 'g'
#define END1 'c'
using namespace std;
/*
	문제 설명

	1. at, gc는 가장 짧은 길이의 KOR 유전자이다.
	2. aXt, gXc도 KOI 유전자이다.
	3. 어떤 X와 Y도 KOR 유전자이면, 이 둘을 연결한 XY도 KOI 유전자이다.
	ex) aattgc , atat 가 있다.

	4. KOI는 DNA 서열 중에서 부분 서열로 되어있다.

	부분 서열 : 임의의 위치에 있는 0개 이상의 문자들을 삭제해서 얻은 서열
*/

string genome;
int dp[MAX][MAX];				// 현재 인덱스 까지 가장 긴 KOI 유전자의 길이
int len;

int solution(int s, int e)
{
	int& result = dp[s][e];
	if (result != -1) return result;

	result = 0;
	if ((genome[s] == START0 && genome[e] == END0) || (genome[s]) == START1 && genome[e] == END1)
	{
		result = solution(s + 1, e - 1) + 2;
	}
	for (int i = s; i < e; i++)
		result = max(result, solution(s, i) + solution(i + 1, e));

	return result;
}

int main()
{
	cin >> genome;
	len = genome.length();
	memset(dp, -1, sizeof(dp));
	cout << solution(0, len - 1);
	return 0;
}