[백준] 9252번 : LCS2(JAVA)

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

9252번: LCS 2

풀이

DP[i][j]
i = 1번째 문자열
j = 2번째 문자열

이런식으로 비교를 하게 됩니다.

dp[i][j] = 1번째 문자열 i번째까지 고려, 2번째 문자열의 j번째까지 고려할 때
만들어 질 수 있는 최장 공통수열의 길이를 구하면 되는 문제입니다.

s[i] == s1[j] ? dp[i-1][j-1] + 1

※ 해설 도움 : raararaara님

 

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		String s = br.readLine(), s1 = br.readLine();
		
		int[][] dp = new int[s.length() + 1][s1.length() + 1];
		
		for(int i = 1; i <= s.length(); i++) {
			for(int j = 1; j <= s1.length(); j++) {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				if(s.charAt(i - 1) == s1.charAt(j - 1)) {
					dp[i][j] = max(dp[i - 1][j - 1] + 1 , dp[i][j]);
				}
			}
		}
		
		String answer = "";
		int i = dp.length - 1, j = dp[0].length - 1;
		while(i != 0 && j != 0) {
			if(dp[i][j] == dp[i - 1][j]) {
				i--;
			}
			else if(dp[i][j] == dp[i][j - 1]) {
				j--;
			}
			else {
				answer += s.charAt(i - 1);
				i--;
				j--;
			}
		}
		System.out.println(dp[s.length()][s1.length()]);
		System.out.print(new StringBuilder(answer).reverse());
	}
	
	public static int max(int a, int b) {
		return a > b ? a : b;
	}
}