백준 7346 (C++) 유전자 함수

문제 이해

틈과 불일치의 페널티를 문제 조건으로 주고 최적 정렬의 총 손해를 알아내는 DNA 서열 정렬 알고리즘을 본 적 있는가?

이 문제는 그 페널티가 각 케이스마다 다르게 2차원 배열로 주어졌다.

최적 정렬을 구하는 계산은 다음 중 하나로 시작한다.
두 배열 X, Y에서

X[0]은 Y[0]과 정렬한다.
X[0]은 틈과 정렬한다.
Y[0]은 틈과 정렬한다.

이 표는 주어진 조건이라 나는 const 2차원 배열로 저장했다.

 

 

 

 

다이나믹 프로그래밍- 점화식

최적 정렬의 손해를 저장하는 2차원 배열 opt를 채우는 점화식을 세우자.

opt[i-1][j-1] + score[ Xseq[i-1]][ Yseq[j-1] ]; 
opt[i-1][j] + score[ Xseq[i-1] ][4]; 
opt[i][j-1] + score[4][ Yseq[j-1] ];​

이때 opt[i][0] 과 opt[0][i] 또한 조건을 고려해 저장한다.

반복문으로 dp를 짠다면 초기 조건이 될 것이다.

코드를 참고하지 않은 채로 이 정보만 가지고 반복문을 짠대도 답에 쉽게 도달할 수 있다.

 

 

 

 

 

코드

#include <iostream>
using namespace std;
using ll = long long;
const int MAX = 101;
const int INF = 1e9;
const int score[5][5] =
        {{5,-1,-2,-1,-3},
        {-1,5,-3,-2,-4},
        {-2,-3,5,-2,-2},
        {-1,-2,-2,5,-1},
        {-3,-4,-2,-1, -INF}}; //

int t, x_length, y_length;
char Xseq[MAX];
char Yseq[MAX];
int opt[MAX][MAX]; // optimal alignment의 비용 2차원 배열

int tran(char c) {
    switch(c){
        case 'A': return 0;
        case 'C': return 1;
        case 'G': return 2;
        case 'T': return 3;
        case '-': return 4;
    }
    return 4;
}

int Max(int a, int b, int c) {
    int t = (a > b) ? a : b;
    return (t > c) ? t : c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> t;
    while (t--) {
        cin >> x_length;
        for (int j = 0; j < x_length; j++) cin >> Xseq[j];
        cin >> y_length;
        for (int j = 0; j < y_length; j++) cin >> Yseq[j];
        
        opt[0][0] = 0;
        
        for (int i = 1; i <= x_length; i++) {
            opt[i][0] = opt[i-1][0] + score[ tran(Xseq[i-1]) ][4];
        }
        for (int i = 1; i <= y_length; i++) {
            opt[0][i] = opt[0][i-1] + score[4][ tran(Yseq[i-1]) ];
        }
        
        for (int i = 1; i <= x_length; i++) {
            for (int j = 1; j <= y_length; j++) {
                // case1 == align X[i] with Y[i]
                // case2 == align X[i] with gap
                // case3 == align Y[i] with gap
                int case1 = opt[i-1][j-1] + score[ tran(Xseq[i-1]) ][ tran(Yseq[j-1]) ];
                int case2 = opt[i-1][j]   + score[ tran(Xseq[i-1]) ][4];
                int case3 = opt[i][j-1]   + score[4][ tran(Yseq[j-1]) ];
                opt[i][j] = Max(case1, case2, case3);
            }
        }
        cout << opt[x_length][y_length] << '\n';
    }
    return 0;
}

 

 

 

 

 

 

 

심화

정렬된 배열을 출력할 수 있다.
opt[x_length][y_length] 의 값을 구하게된 경로를 추적한다.

if(c1 == max( c1, c2, c3 )) P[i][j] = 1; 
if(c2 == max( c1, c2, c3 )) P[i][j] = 2; 
if(c3 == max( c1, c2, c3 )) P[i][j] = 3;

이런 식으로 추가적인 2차원 배열 P를 사용한다.
그 다음 이 배열을 역추적한다.
참고로만 적은 코드이다.

/* 재귀로 case를 역추적해서 input된 dna 데이터 정렬함 */
void align(int x, int y) {
    int loc = x;
    if(x == m && y == n) loc = (x > y) ? x : y; // align_ans의 크기는 얼마인가?
    
    if(P[x][y] == 1) { // align X[x] and Y[y]
        align_ans[1][loc] = Xseq[x];
        align_ans[2][loc] = Yseq[y];
        align(x - 1, y - 1);
    }
    if(P[x][y] == 2) { // align X[x] and gap
        align_ans[1][x] = Xseq[x];
        align_ans[2][x] = '-';
        align(x - 1, y);
    }
    if(P[x][y] == 3) { // align gap and Y[y]
        align_ans[1][y] = '-';
        align_ans[2][y] = Yseq[y];
        align(x, y - 1);
    }
}