boj, 백준) 2306. 유전자 ( C / C++)

1. 문제 링크

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

2306번: 유전자

2. 문제 개요

DNA 서열은 4개의 문자로 이루어진 문자열이다.

 

(1) at와 gc는 가장 짧은 길이의 KOI 유전자이다.

(2) 어떤 X가 KOI유전자라면, aXt, gXc도 KOI 유전자이다.

(3) 어떤 X, Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다.

 

문제에서 주어진 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI유전자를 찾아 그 길이를 출력하는 프로그램을 만들자.

 

3. 문제 힌트

   DP 문제.

(2), (3)의 조건을 만족시켜주어야 한다.

dp[l][r]을 l번 index부터 r번 index까지 KOI유전자의 최대 길이라고 두자.

 

(3) 번 규칙 -> dp[l][k] + dp[k+1][r]을 고려해보자 ( l <= k < r)

(2) 번 규칙 -> if( str[l] == a,g 이고, str[r] == t,c) 라면, dp[l+1][r-1] + 2를 고려해보자.

 

4. 문제 풀기

처음에 이 문제 접근방식에 조금 고생을 했다. 

2개짜리를 찾아서 그걸 기반으로 만들어 나갈지, 재귀 형식으로 분할해서 나갈지.. 등등 고생을 했다.

 

결국엔 이 문제도 완전 탐색 같은 느낌인데 dp를 이용해서 시간 복잡도를 줄이는 형식이다. 

고려할 점은 문제에 다 나와있었다.

(2) 번 규칙처럼 양끝이 KOI유전자인 경우를 살펴볼 수 있겠고,

(3) 번 규칙처럼 어느 2개가 쪼개진게 붙어진 경우가 있을 수 있겠다.

 

(3)번 규칙을 생각해볼 때, 그럼 KOI유전자 3개가 붙어서 된 경우는 어떻게 찾을까?라는 생각을 할 수 있을 텐데

1 덩이 + 2덩이 이렇게 붙고, 2덩이 부분은 재귀함수에 의해서 1덩이 + 1덩이 = 2 덩이로 구해진 최댓값이라 고려할 필요가 없어진다. 

 

(2) 번 규칙은 양 끝이 KOI이고 그 내부를 또 작은 문제로 쪼개어서 생각할 수 있기 때문에 저런 식으로 dp 식을 세워 구현해주었다.

5. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

string s;
int dp_table[500][500];

int dp(int l, int r)
{
	if (l >= r)	return 0;

	int &cache = dp_table[l][r];
	if (cache != -1)return cache;

	int ans = -1;

	for (int k = l; k < r; ++k) 
		ans = max(ans, dp(l, k) + dp(k + 1, r));
	
	if ((s[l] == 'a' && s[r] == 't') || (s[l] == 'g' && s[r] == 'c'))
		ans = max(ans, dp(l + 1,r - 1) + 2);

	return  cache = ans;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(dp_table, -1, sizeof(dp_table));

	cin >> s;

	cout << dp(0, s.length() - 1);
	
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~