LCS 최장 공통 부분 수열

2021-01-19

LCS

백준 9251번

LCS의 관계를 정의한 함수를 이용하여 DP를 통해서 길이를 구하는 문제

참고 설명 : 

ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4#cite_note-BHR00-2

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

내가 만든 소스 코드

import java.io.*;
public class Main {
	static char[] A;
	static char[] B;
	static String [] lcs(int aIndex, int bIndex) {
		String [] result = {""};
		if(aIndex == -1 || bIndex == -1) return result;
		if(A[aIndex] == B[bIndex]) {
			result = lcs(aIndex - 1, bIndex -1);
			for(int i = 0; i< result.length; i++) {
				result[i] += A[aIndex];
			}
		}
		else {
			String[] one = lcs(aIndex -1, bIndex);
			String[] two = lcs(aIndex, bIndex -1);
			if(one[0].length() > two[0].length()) {
				result = one;
			}
			else if(one[0].length() < two[0].length()){
				result = two;
			}
			else {
				String[] tem = new String[one.length + two.length];
				for(int i = 0; i< tem.length; ) {
					for(int a = 0; a<one.length; a++) {
						tem[i] = one[a];
						i++;		
					}
					for(int b = 0; b<two.length; b++) {
						tem[i] = two[b];
						i++;
					}
				}
				result = tem;
			}
		}
		return result;
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//입력
		A = br.readLine().toCharArray();
		B = br.readLine().toCharArray();
		//계산
		int [][] dp = new int[A.length+1][B.length+1];
		for(int a = 0; a < A.length; a++) {
			for(int b = 0; b < B.length; b++) {
				if(A[a] == B[b]) dp[a+1][b+1] = dp[a][b] + 1;
				else {
					dp[a+1][b+1] = Math.max(dp[a][b+1], dp[a+1][b]);
				}
			}
		}
		//출력
		bw.write(dp[A.length][B.length]+"\n");
		for(String s : lcs(A.length -1, B.length -1)) bw.write(s + "\n");
		br.close();
		bw.flush();
		bw.close();
	}
}