백준온라인 2306번 [유전자][C++]

www.acmicpc.net/problem/2306

2306번: 유전자

---

나의 풀이 

최대 길이가 정의되는 경우는 1) KOI유전자 + KOI유전자 또는 2) KOI유전자 안에 KOI유전자 가 들어가 있는 구조이므로

최대길이를 구하려고 할 때는 작은 것부터 결과를 이끌어내는 다이내믹 프로그래밍으로  풀어야 된다고 생각했다.

 

입력으로 주어진 문자열을 S라고 할 경우

i <=j 인 인덱스에 대하여 $dp[i][j]$를 정의할 수 있다.

 

$dp[i][j]$를 i index부터 j index까지 이루어진 문자열의 최대 KOI유전자 길이라 하면

 

위에서 정의한 두 가지만 판별해주면 된다

 

$S[i]$와 $S[j]$ 같을 경우 경우 1에 해당이 되므로 $dp[i+1][j-1]+2$ 로 초기화 해준후

 

$S[i]$부터  $S[j]$ 까지 경우 2처럼 쪼개어 봤을 때 더 큰 최대 길이 인지도 고려하여 주면 된다.

 

---

코드

	#include <bits/stdc++.h>
	using namespace std;
	int d[501][501];
	string s;
	bool isKOI(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(nullptr);
	cin>>s;
	int n = s.length();
	for(int k=1;k<n;k++){
	for(int i=0;i+k<n;i++){
	if(isKOI(s[i],s[i+k])){
	d[i][i+k]=d[i+1][i+k-1]+2;
	}
	for(int j=i;j<i+k;j++){
	d[i][i+k] = max(d[i][i+k],d[i][j]+d[j+1][i+k]);
	}
	}
	}
	cout<<d[0][n-1];
	}

view raw .cpp hosted with ❤ by GitHub