[BOJ 2306] 유전자

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

 

- 문제 요약

 

DNA 서열은 4개의 문자 {a,c,g,t}로 이루어진 문자열이다.

또한 KOI 유전자는 아래의 3가지 조건을 만족한다.

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

주어진 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI 유전자를 찾아 그 길이를 출력하시오.

 

 

- 알고리즘 정리

 

DP[a][b] : (s[a], s[b]) 구간에서 KOI 유전자의 최대 길이

 

우선 위와 같이 DP 테이블 정의를 해 줍니다.

 

문제에서 제시한 조건을 보면

(1) KOI 유전자가 쭉 이어져 있는 경우. ex) atat

(2) KOI 유전자 안에 KOI 유전자가 들어가 있는 경우. ex) gaattc

이렇게 두 가지 경우가 있다는 것을 알 수 있습니다.

 

각 경우에 대하여 식을 따로따로 세워주고 max값을 구해주는 방식으로 접근하면 좋습니다.

1번의 경우 식은 => dp[a+1][b-1] = 2; (KOI 유전자의 최소 길이로 초기화)

2번의 경우 식은 => dp[a][a+x] = max(dp[a][a+x], dp[a][b] + dp[b+1][a+x]); (구간을 나눠서 max값 찾기)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define MAX 2005
typedef long long ll;
string s;
int dp[MAX][MAX];

//DP[a][b] : (s[a], s[b]) 구간에서 KOI 유전자의 최대 길이 

bool f(char a,char b){
	if((a=='a' && b=='t') || (a=='g' && b=='c')){
		return true;
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s;
	for(int x=1;x<s.length();x++){
		for(int i=0;i+x<s.length();i++){
			if(f(s[i],s[i+x])){
				dp[i][i+x]=dp[i+1][i+x-1]+2;	
			}
			for(int j=i;j<i+s.length();j++){
				dp[i][i+x]=max(dp[i][i+x],dp[i][j]+dp[j+1][i+x]);
			}
		}
	}
	cout<<dp[0][s.length()-1]<<endl;
}

문제 풀이 성공

 

+) 처음에 왜 틀렸나 싶었습니다.

+) 저처럼 틀리지 마시고... 배열 인덱스가 넘어갈 걸 고려해서 DP 테이블 크기를 넉넉하게 잡아주시는 걸 추천드립니다.