[백준] 2306번 유전자 (C++)

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

 

 

최근 dp유형이 좀 많이 약한것 같아서 다양한 문제들을 풀면서 dp에 익숙해지기로 하였다.

 

이 문제는 문자열이 주어지고 (a, t), (g, c) 라는 가장 짧은 KOI 유전자가 존재하며

KOI 유전자에 겹쳐서 성립하는 경우도 KOI 유전자라고 하며 이때 최대 길이를 구하는 문제이다.

 

문제 조건에 최대 길이의 KOI 문자열을 구하기 위해서 문자 중간중간을 삭제할 수 있으며 제한은 없다.

 

따라서 내가 해당 문자를 선택하고 버리는 것에 따라서 미래에 영향을 주기 때문에 모든 경우의 수를 구하며 최적화를 해야한다.

 

따라서 dp 테이블을 정의해야한다.

 

스스로 해결: ❌

 

dp[i][j] = i구간부터 j구간까지 KOI 문자열의 최대 길이

로 식을 세우고 점화식을 구성해보았다.

 

최대 길이가 500이므로 N^2, N^3으로도 풀이가 가능하기 때문에

 

큰 문제 : [0, 길이 - 1] 전체 문자열에서 최대 KOI 문자열의 길이

부분 문제 : [l, r] 구간에서 최대 KOI 문자열의 길이

로 생각해서 접근했다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

struct Tree {
    int Node, left, right;
};

const int INF = 1e9;
const int MAX = 20001;
const int D = 2000000;
const int MOD = 10007;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dp[501][501];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    string s;

    cin >> s;

    int answer = 0;

    for(int l = 1; l <= s.size(); l++) {     // 문자 길이
        for(int i = 0; i + l -1 < s.size(); i++) {     // 시작점
            int j = i + l - 1;      // 끝점

            if((s[i] == 'a' && s[j] == 't') || (s[i] == 'g' && s[j] == 'c')) {
                dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2);
                answer = max(answer, dp[i][j]);
            }

            for(int k = i; k < j; k++) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
                answer = max(answer ,dp[i][j]);
            }
        }
    }

    cout << answer;
}

 

핵심 코드를 살펴보면

    for(int l = 1; l <= s.size(); l++) {     // 문자 길이
        for(int i = 0; i + l -1 < s.size(); i++) {     // 시작점
            int j = i + l - 1;      // 끝점

            if((s[i] == 'a' && s[j] == 't') || (s[i] == 'g' && s[j] == 'c')) {
                dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2);
                answer = max(answer, dp[i][j]);
            }

            for(int k = i; k < j; k++) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
                answer = max(answer ,dp[i][j]);
            }
        }
    }

 

문자 길이에 따라 작은 문제를 풀며 큰 문제를 풀 수 있도록 구성하였으며

이때 시작점 i는 0부터 최대길이까지 가능하기 때문에 i + l -1을 해주었다. -1을 한 이유는 아시다시피 인덱스는 0부터 시작하기 때문에 -1을 처리하였다.

 

시작점과 끝점이 같은 경우 시작점에서 한칸 이전 , 도착점에서 한칸 이전 즉 시작점은 가운데에서 왼쪽으로 퍼지고 끝점은 가운데에서 오른쪽으로 퍼지기 때문에 이전값 [i+1][j-1]값을 가져와서 현재 같은 값의 길이 2를 더해주었다.

 

또한 k지점같은 경우 해당 지점 문자를 버릴 수 있기 때문에 시작점에서부터 끝점까지 반복하여 버리는 경우와 왼쪽 구간과 오른쪽 구간을 나눠서 더 큰 값으로 갱신하는 경우를 동시에 찾고 있다.

 

즉 k값이 i 또는 j-1일때 각 지점은 문자를 버리는 것이고 그 외의 지점들은 문자를 나눠서 최대길이를 갱신하는것이다.

 

탑다운 정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

struct Tree {
    int Node, left, right;
};

const int INF = 1e9;
const int MAX = 20001;
const int D = 2000000;
const int MOD = 10007;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dp[501][501];
string s;

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

    int &ret = dp[l][r];

    if(ret != -1) return ret;

    for(int i = l; i < r; i++) {
        ret = max(ret, func(l, i) + func(i+1, r));
    }

    if((s[l] == 'a' && s[r] == 't') || (s[l] == 'g' && s[r] == 'c')) {
        ret = max(ret, func(l+1, r-1) + 2);
    }

    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> s;

    memset(dp, -1, sizeof(dp));

    cout << func(0, s.size()-1);
}

 

마찬가지로 나올 수 있는 경우를 쪼개서 구해주었다.

 

 

회고록

dp를 풀기전 무조건 점화식만 생각하지말고 dp라고 감이 잡히는 경우 큰 문제와 부분 문제를 정의할 수 있는지 판별하여

할 수 있는 행동을 나누고 점화식을 세우자