BOJ 2306

10 Apr 2020 • ProblemSolving

유전자

문제출처

문제 해석

  • DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI 유전자를 찾는 문제입니다.
  • KOI 유전자는 다음의 조건을 만족합니다.
    1. at,gc는 가장 짧은 길이의 KOI 유전자입니다.
    2. 어떤 X가 KOI 유전자라면, aXt와 gXc도 KOI유전자입니다.
    3. 어떤 X와 Y가 KOI 유전자라면,XY도 KOI유전자입니다.
  • 부분서열이란 주어진 서열에 임의의 문자를 0개 이상 삭제하여 얻어진 수열을 의미합니다.

설계(X)

  • DP문제입니다.
  • 점화식은 D[i][j] = “i~j의 부분수열중 KOI길이 최댓값”으로 설정합니다.
  • 점화식은 설정하였으나, 재귀 함수 구현부분에서 잘못된 점을 디버깅하지 못하여 kks227님의 코드를 참조하였습니다.
  • 먼저, 현재 위치의 문자를 지우는 경우와 지우지 않는 경우로 나눌 수 있습니다.
  • 지우는 경우 dp(cur+1,end)로 최댓값을 갱신합니다.
  • 지우지 않는 경우에서 현재 문자가 ‘a’또는 ‘g’인 경우만 고려합니다.
  • i = cur+1~end-1까지 탐색하여 짝이 되는 문자를 찾을 시, dp(cur+1,i)+dp(i+1,end)의 최댓값을 찾습니다.
  • 이에 더해서 가장 짧은 KOI유전자가 생성된 것이므로 2를 더해줍니다.

구현(X)

코드
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 501
string s;
int N;
int cache[MAXN][MAXN];
int dp(int cur, int end){
    if (cur == N || cur == end) return 0;
    int& ret = cache[cur][end];
    if (ret !=-1) return ret;
    // 지우는 경우
    ret = max(ret,dp(cur+1,end));
    // 안지우는 경우
    if (s[cur] =='a'){
        for (int i = cur +1; i < end; i++){
            if (s[i] == 't'){
                ret = max(ret,dp(cur+1,i)+dp(i+1,end)+2);
            }
        }
    }
    else if (s[cur]=='g'){
        for (int i = cur +1; i < end; i++){
            if (s[i] == 'c'){
                ret = max(ret,dp(cur+1,i)+dp(i+1,end)+2);
            }
        }
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(cache,-1,sizeof(cache));
    cin >> s;
    N = s.length();
    cout << dp(0,N) <<"\n";
    return 0;
}
디버깅
  • 제가 구현했던 코드의 경우에는 ‘a’와 ‘g’를 따로 구분하지 않고 하나의 반복문에서 처리해줬습니다. 이부분에서는 문제가 없으나, 범위를 cur+1~N으로 잘못 설정하여 논리적 오류가 났습니다.
  • 또한, MAX값을 500으로 설정하여 최대값인 500개의 부분수열을 찾을 수 없었습니다.
제출결과
  • 0 ms

마무리

  • DP를 활용한 문제였습니다. 사소한 오류로 인해 제대로 구현하지 못했습니다.
 BOJ

Related Posts