[백준 9251] LCS - 자바

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

9251번: LCS

 

1. 풀이

---

우선 LCS에 대해서 이해를 해야 한다고 생각합니다.

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

 

즉, bcba는 abcbdab와 bdcaba의 LCS입니다.

 

이 문제를 처음 접했을때, 여러가지 생각을 해봤지만, 끝내 못 풀고 구글링을 통해 해결을 했습니다.

 

참고한 블로그와 강의는 아래에 남겨 놓겠습니다.

 

풀이법은 행(입력한 문자열중 하나)에서 현재까지 나온 문자열과 열(입력한 문자열중 나머지)에서 현재까지 나온 문자열 사이의 LCS 길이를

메모이제이션에 계속해서 저장해서 순환식을 세우는 문제였습니다.

 

순환식은 아래와 같습니다.

 

if(x[i] == y[i])
	memo[i][j] = memo[i - 1][j - 1] + 1;
else
	memo[i][j] = max(c[i-1][j], c[i][j-1]);

 

이해를 위해 아래 설명을 넣었습니다.

 

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0
A	0
P	0
C	0
A	0
K	0

 

(1) 위와 같이 패딩을 해줍니다.

 

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0
P	0
C	0
A	0
K	0

 

(2) 비교하는 위치의 문자가 같으면 현재 위치 값 : 왼쪽 대각선 값 + 1

     비교하는 위치의 문자가 같지 않으면 현재 위치 값 : max(왼쪽 값, 위쪽 값)

 

그렇게 쭉 하다보면 아래와 같은 메모이제이션이 완성됩니다.

 

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

정답은 ACAYKP와 CAPCAK에 대해서 메모이제이션에 저장한 4 입니다.

 

만약 ACAY와 CAP의 LCS값을 찾고 싶으면 2가 정답입니다.

 

2. 코드

---

import java.util.*;

public class Main {
	
	public static int max(int a, int b) {
		if(a > b)
			return a;
		else
			return b;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String a = sc.next();
		String b = sc.next();
		
		int[][] memo = new int[a.length()+1][b.length()+1];
		
		// 0으로 패딩 ( a를 세로, b를 가로 설정합니다.) 
		for(int i = 0; i <= a.length(); i++)
			memo[i][0] = 0;
		for(int i = 0; i <= b.length(); i++)
			memo[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))
					memo[i][j] = memo[i-1][j-1] +1;
				else 
					memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
			}
		}
		
		System.out.println(memo[a.length()][b.length()]);
		
		sc.close();
		return;
	}
}