[백준] 9251 LCS [자바]

 

---

https://st-lab.tistory.com/139

[백준] 9251번 : LCS - JAVA [자바]

http://melonicedlatte.com/algorithm/2018/03/15/181550.html

[백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static String str, str1;
	static Integer[][] dp;
 	public static void main(String arg[]) throws Exception {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		str = br.readLine();
 		str1 = br.readLine();
 		dp = new Integer[str.length()][str1.length()];
 		int result = LCS(str.length() - 1, str1.length() - 1);
 		System.out.println(result);
 	}
 	static int LCS(int x, int y) { //x == str y == str1
 		if(x == -1 || y == -1) {
 			return 0;
 		}
 		if(dp[x][y] != null)
 			return dp[x][y];
 		if(str.charAt(x) == str1.charAt(y)) {
 			return dp[x][y] = LCS(x-1, y-1) + 1;
 		}
 		else { //같지않다면 직전의 값(위, 왼쪽) 중 큰 값
 			return dp[x][y] = Math.max(LCS(x-1,y), LCS(x, y-1));
 		}
 	}
}