BOJ 9251 LCS Java

BOJ 9251 LCS Java

 

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

9251번: LCS

 

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		s1 = br.readLine();
		s2 = br.readLine();
		
		arr = new int[s1.length()+1][s2.length()+1];
		for (int i = 1; i <= s1.length(); i++) {
			for (int j = 1; j <= s2.length(); j++) {
				arr[i][j] = -1;
			}
		}
		
		solve();

	} // main
	
	static String s1, s2;
	static int[][] arr;
	static void solve() {
		
		for (int i = 1; i <= s1.length(); i++) {
			for (int j = 1; j <= s2.length(); j++) {
				if(s1.charAt(i-1) != s2.charAt(j-1)) 
					arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
				else 
					arr[i][j] = arr[i-1][j-1] + 1;
			}
		}
		
		System.out.println(arr[s1.length()][s2.length()]);
 		
	} // solve
}

 

LCS 넘 오랜만이라 설명 참고했다..

풀이를 어떻게 할 지만 생각이 들고 그게 코드로 나오지가 않는다

dp 는 아직도 어렵다......

 

arr[i][j] 는 문자열1의 0~i, 문자열2의 0~j까지 비교한 LCS이다.

그래서 arr[i][j]가 i j 같은 문자일 때 i번째 문자와 j번째 문자를 고려하지 않은 결과인 arr[i-1][j-1]에 1을 더한 것과 같다.

 

i j 다른 문자일 때는 0~i 와 0~j-1 을 봤을 때 혹은 0~i-1 와 0~j 를 봤을 때 더 큰 값이 들어 가면 된다

 

예로 들어 ACB, CBF 일 때

arr[2][2] 는 AC와 C의 LCS(1) 혹은 A와 CB의 LCS(0) 중 큰 값이 되는 것이다.