[Java] BOJ 9252번 LCS2

9252번: LCS 2

---

풀이

DP와 재귀를 사용하여 해결했습니다.

---

코드

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

public class Main {
	public static String S1, S2;
	public static int[][] memo;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		S1 = br.readLine();
		S2 = br.readLine();
		
		int len1 = S1.length();
		int len2 = S2.length();
		
		memo = new int[len1 + 1][len2 + 1];
		
		for (int i = 1; i <= len1; ++i) {
			for (int j = 1; j <= len2; ++j) {
				
				if (S1.charAt(i - 1) == S2.charAt(j - 1)) {
					// 문자가 같다면 이전 문자까지의 LCS에 +1을 해주어야하는데
					// S1 문자열일 경우 현재 문자의 이전 문자는 i - 1이고
					// S2 문자열일 경우 현재 문자의 이전 문자는 j - 1이 되므로
					// S1, S2 둘다의 이전 문자의 LCS는 memo[i - 1][j - 1]이 된다.
					memo[i][j] = memo[i - 1][j - 1] + 1;
				}
				else {
					// 문자가 다를경우 S1 문자열의 이전 문자까지의 LCS 즉, memo[i - 1][j]와
					// S2 문자열의 이전 문자까지의 LCS 즉, memo[i][j - 1] 중 큰 값을 선택하면 된다.
					memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
				}
			}
		}
		
		System.out.println(memo[len1][len2]);
		System.out.println(print(len1, len2));
	}
	
	public static String print(int i, int j) {
		if(i == 0 || j == 0) {
			return "";
		} else if(S1.charAt(i - 1) == S2.charAt(j - 1)) {
			return print(i - 1, j - 1) + S1.charAt(i - 1);
		} else {
			if(memo[i][j - 1] > memo[i - 1][j])
				return print(i, j - 1);
			else
				return print(i - 1, j);
		}
	}
}

---

pyo7410/Algorithm