[Java] 백준 9251번 LCS

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

9251번: LCS

 

LCS(Longest Common Subsequence) 란 최장 공통부분 수열을 의미한다.

예제에서 ACAYKP, CAPCAK의 LCS는 

ACAYKP

CAPCAK 이다.

 

테이블을 그려 이해해보자.

테이블을 그리면 다음과 같다.

 

규칙을 찾아보면

1) x번째 원소와 y번째 원소의 값이 같을 때

C의 경우, AC와 C의 공통부분은 {C} 하나로 길이가 1이다.

3) x번째 원소와 y번째 원소의 값이 다를 때,

왼쪽 값과 위쪽 값을 비교하여 최댓값이 최장 공통부분 수열의 길이이다

2)

ACA와 CA의 공통부분은 {CA}로 길이가 2이다.

이는 노란색 부분 기준 왼쪽과 위쪽의 최댓값에 현재 값인 A가 공통되므로 +1을 해준 것이다.

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String a = sc.next();
		String b = sc.next();
		
		int[][] dp = new int[a.length()+1][b.length()+1];
		
		// 0으로 패딩 
		for(int i = 0; i <= a.length(); i++)
			dp[i][0] = 0;
		for(int i = 0; i <= b.length(); i++)
			dp[0][i] = 0;
		
	
		for(int i = 1; i <= a.length(); i++) {
			for(int j = 1; j <= b.length(); j++) {
				if(a.charAt(i-1) == b.charAt(j-1))
					dp[i][j] = dp[i-1][j-1] +1;
				else 
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
			}
		}
		
		System.out.println(dp[a.length()][b.length()]);
		
		sc.close();
		return;
	}
}