DNA 유사도 (정올 1858, 백준 2612)

문제 설명

LCS 응용

두 DNA 가 같은 위치에 있으면 +3 다르면 -2점을 더한다.

최대 점수와 두 DNA 에서 점수가 제일 높은 구간을 각각 출력한다.

 

문제 링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1131&sca=99&sfl=wr_hit&stx=1858

JUNGOL

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

2612번: DNA 유사도

 

풀이

LCS 이론 

일반 LCS 기본 로직은 같지만,  마지막에 최대가 되는 구간을 역추적해 주어야 한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int la=Integer.parseInt(br.readLine());
		String a=br.readLine();
		int lb=Integer.parseInt(br.readLine());
		String b=br.readLine();//입력
		int dp[][]=new int[la+1][lb+1];
		for(int i=1;i<=la;i++) {
			for(int j=1;j<=lb;j++) {
				if(a.charAt(i-1)==b.charAt(j-1)) {
					dp[i][j]=dp[i-1][j-1]+3; 
				}else {
					dp[i][j]=Math.max(Math.max(dp[i-1][j-1],Math.max(dp[i-1][j], dp[i][j-1]))-2,0);//왼쪽 대각선 위 중 최대에서 점수 -2. (0밑으로 내려가면 0으로)
				}
			}
		}//LCS
		int max=Integer.MIN_VALUE;
		int x=0;
		int y=0;
		for(int i=1;i<=la;i++) {
			for(int j=1;j<=lb;j++) {
				if(max<dp[i][j]) {
					max=dp[i][j];
					y=i;
					x=j;
				}
			}
		}//최대값 및 최대 구간의 끝점 찾기
		int inity=y;
		int initx=x;
		while(dp[y][x]!=0) {//시작점이거나 0밑으로 점수가 내려가서 끊는게 나은 부분이 나올때까지 돌림 
			if(dp[y-1][x]==dp[y][x]+2) {
				y--;
			}
			else if(dp[y][x-1]==dp[y][x]+2) {
				x--;
			}
			else {
				x--;
				y--;
			}
		}//최대구간의 시작점 역추적
		System.out.println(max);
		for(int i=y+1;i<=inity;i++) {
			System.out.print(a.charAt(i-1));
		}
		System.out.println();
		for(int i=x+1;i<=initx;i++) {
			System.out.print(b.charAt(i-1));
		}
	}
}