[백준] 9252 - LCS 2

[문제링크]

9252번: LCS 2

0. 기본 LCS 알고리즘 : 문자열 A와 B의 끝 문자가 x로 같다면, LCS의 길이는 A'와 B'의 LCS + 1 이다

  - 여기서 A', B'이란 맨 끝문자를 제외한 A, B

  - A = A'+x, B = B'+x

  - A와 B의 끝 문자가 x,y로 다르다면, LCS의 길이는 A'와 B의 LCS, A와 B'의 LCS 둘 중 큰 쪽이다

  - A = A'+x, B = B'+y

 

1. 위 과정을 DP로 계산하면서 모든 계산 결과를 저장한다

 

2. LCS문자열 찾기 : DP를 역으로 추적한다

  - DP[x][y]의 값이 DP[x][y-1]와 같다면 : 해당 칸으로부터 온 값, y--

  - DP[x][y]의 값이 DP[x-1][y]와 같다면 : 해당 칸으로부터 온 값, x--

  - 둘 다 아니라면 : LCS로서 진행된 칸, x--, y--, 해당 위치의 문자를 저장

 

3. 역순으로 찾았으므로, 뒤집어서 출력해준다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String fst = br.readLine();
		String snd = br.readLine();
		
		int len = fst.length();
		int sndLen = snd.length();
		
		int[][]dp = new int[len+1][sndLen+1];
		
		for (int i = 0; i < len; i++) {
			char f = fst.charAt(i);
			for (int j = 0; j < sndLen; j++) {
				char s= snd.charAt(j);
				
				if(s==f) {
					dp[i+1][j+1] = 1 + dp[i][j];
				}
				else {
					dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
				}
			}
		}
		
		int x = len, y=sndLen;
		while(sb.length()!=dp[len][sndLen]) {
			if(dp[x][y]==dp[x][y-1]) {
				y--;
			}else if(dp[x][y]==dp[x-1][y]) {
				x--;
			}else {
				x--;y--;
				sb.append(fst.charAt(x));
			}
		}
		
		System.out.println(dp[len][sndLen]);
		System.out.println(sb.reverse());
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면