백준 동적계획법 - 9215번 : LCS

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

9251번: LCS

---

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String a = br.readLine();
		String b = br.readLine();
		char[] ac = a.toCharArray();
		char[] bc = b.toCharArray();
		int[][] memo = new int[a.length()+1][b.length()+1];
		for(int i=0; i<a.length();i++) {
			for(int j=0; j<b.length(); j++) {
				if(ac[i]==bc[j]) {
					memo[i+1][j+1] = memo[i][j]+1;
				}
				else {
					memo[i+1][j+1] = Math.max(memo[i+1][j], memo[i][j+1]);
				}
			}
		}
		bw.write(memo[memo.length-1][memo[0].length-1]+"");
		bw.close();
	}
}