백준 9251번 : LCS (Java)

 문제

9251 LCS

 

 구현 방법

LCS (Longest Common Subsequence)는 최장 공통 부분 수열로 모두의 부분 수열이 되는 수열 중 가장 긴 값을 찾는 알고리즘 입니다. 부분 수열이기 때문에 연속할 필요가 없습니다.

 

2차원 배열을 생성하여 문자를 하나씩 비교해주었습니다.

아래 순서는 구현 과정을 간략하게 나타낸 것 입니다.

1. 편의를 위해 마진 설정
2. 문자가 같다면 이전에 저장된 값에 +1 (이전에 저장된 값에는 현재까지의 최장 부분 수열 길이가 저장)
3. 문자가 같지 않다면 현재까지 탐색한 부분 수열 길이에서 더 큰 값 저장
4. 위 과정 반복

코드를 보고 따라가면서 이해하는 것을 추천드립니다.

 

 구현 코드

package BOJ.Gold;

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

public class B9251_LCS {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String A = br.readLine();
		String B = br.readLine();
		int[][] LCS = 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 (i==0 || j==0) LCS[i][j] = 0;
				// 문자가 같다면 이전 문자에 저장된 값 + 1
				else if (A.charAt(i-1) == B.charAt(j-1)) LCS[i][j] = LCS[i-1][j-1] + 1; 
				// 문자가 다르다면 현재까지 탐색한 문자에서 더 큰 값 저장
				else LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
			}
		}
		System.out.println(LCS[A.length()][B.length()]);
	}
}

 

정답!