[백준]LCS2(9252번)

https://www.acmicpc.net/problem/9252
//1 문제 분석

LCS의 길이를 구하고 그 값을 출력하는 문제이다.

//2 문제 해결

기본적인 알고리즘은 과거 블로그에서 본적이 있어서 그 기억을 토대로 작성하였다. LCS를 다이나믹 프로그래밍으로 구하는 기본 로직은 다음과 같다.
끝이 다른 두 문자열 예를들어 ACAYKP, CAPCAK 의 LCS는 ACAYKP와 CAPCA의 LCS와 ACAYK,CAPCAK의 LCS중 큰 것과 같다.
반면 끝이 같은 경우 예를들어 ACA와 CAPCA의 LCS의 경우 이는 AC와 CAPC의 LCS에 A를 더한 것과 같다.
LCS는 기본적으로 두번째 경우로만 값이 늘어나니 dp 배열에서 두번째 경우가 적용된것을 탐색하면 LCS의 값 역시 찾을 수 있다.

//3 작성 코드

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

public class LSC2_9252 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] s1 = br.readLine().toCharArray();
		char[] s2 = br.readLine().toCharArray();
		int[][] dp = new int[s1.length+1][s2.length+1];
		for (int i = 1 ; i<s1.length+1 ; i++) {
			for (int j = 1 ; j<s2.length+1; j++) {
				if(s1[i-1]!=s2[j-1]) {
					dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
				} else {
					dp[i][j]=dp[i-1][j-1]+1;
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(dp[s1.length][s2.length]).append("\n");
		StringBuffer ans = new StringBuffer();
		int r = s1.length;
		int c = s2.length;
		int temp = dp[r][c];
		while(temp!=0) {
			if (temp==dp[r-1][c]) {
				r--;
			} else if (temp==dp[r][c-1]) {
				c--;
			} else {
				ans.append(s1[r-1]);
				r--;
				c--;
			}
			temp=dp[r][c];
		}
		sb.append(ans.reverse());
		System.out.println(sb);
	}
}

//4 시행착오

처음에 LCS문자열을 출력하기 위해 마지막 좌표에서부터 역으로 과정을 탐색할 때, 값을 그대로 StringBuilder에 넣어서 역순의 LCS가 출력되었다. 이를 고치기 위해 StringBuffer을 선언한 후 여기에 값을 저장하고 마지막에 reverse메서드를 통해 값을 뒤집은 후 출력하였다.