BOJ - DNA 유사도(2612)

문제(링크)

LCS 알고리즘 응용문제입니다.

dp[i][j] = i, j 지점에서 나올 수 있는 최대 유사도

공백을 추가할 때, 현재 유사도가 음수가 되버리면 그 지점부터 다시 시작하는게 이득입니다.
따라서 lcs 알고리즘과 비슷하게 문자가 같지 않다면 왼쪽, 왼쪽 위, 위 값의 최댓값을 현재 값으로 가져오는데
해당 값에 공백을 추가한 값, 즉, -2 를 한 값을 가져오고 최종 값이 음수가 되면 0으로 바꿔줘야 합니다.

문자가 같다면 lcs 알고리즘에서 처럼 +3을 해줍니다.

dp 배열을 완성했다면 유사도가 최대인 점을 찾습니다.
최대인 점으로부터 가로, 세로, 대각선을 체크하면서 시작 점을 찾아가는데,
가로, 세로는 +2 , 대각선은 -3 으로 찾아가면서 0이 될때까지 찾아가고, 역으로 시작점부터 끝점까지 출력하면 됩니다.

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vii vector<pii>
#define IMAX 2000000001
#define LMAX 1000000000000000000
#define DMAX 0xFFFFFFFFFFFFF
int mv1[4] = { 0, 1, 0, -1 };
int mv2[4] = { 1, 0, -1, 0 };

int n, m;
string str1, str2;
int dp[1001][1001];

int main(void) {
 FIO;

 cin >> n >> str1 >> m >> str2;

 for (int i = 1; i <= n; i++)
 {
  for (int j = 1; j <= m; j++)
  {
   if (str1[i - 1] != str2[j - 1]) {
    //음수가 되면 0으로 바꿔줌
    dp[i][j] = max(max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1])) - 2, 0);
   }
   else {
    dp[i][j] = dp[i - 1][j - 1] + 3;
   }
  }
 }

 int maxLeng = -500000;
 int init_x, init_y;

 for (int i = 1; i <= n; i++)
 {
  for (int j = 1; j <= m; j++)
  {
   if (dp[i][j] > maxLeng) {
    //유사도가 가장 높은 곳이 끝 점
    maxLeng = dp[i][j];
    init_x = i;
    init_y = j;
   }
  }
 }

 int x = init_x, y = init_y;

 while (dp[x][y] != 0) {
  //시작 점 탐색
  if (dp[x - 1][y] == dp[x][y] + 2) {
   x--;
  }
  else if (dp[x][y - 1] == dp[x][y] + 2) {
   y--;
  }
  else {
   x--;
   y--;
  }
 }

 cout << maxLeng << "\n";

 //각 문자열마다 시작 점 ~ 끝 점 출력
 for (int i = x + 1; i <= init_x; i++)
 {
  cout << str1[i - 1];
 }

 cout << "\n";

 for (int i = y + 1; i <= init_y; i++)
 {
  cout << str2[i - 1];
 }
}