Baekjoon_9251_LCS

문제 설명

9251번: LCS

• 두 개의 수열이 주어졌을 때
• 두 수열의 공통된 부분 수열 중 가장 긴 부분 수열의 길이를 출력 

 

문제 풀이

LCS(Longest Common Subsequence, 최장 공통 부분 문자열)은 DP를 이용해 문제를 해결해야 한다.

 

LCS는 다음 3가지 경우로 나눌 수 있다.

1. 비교 수열의 길이가 0 인 경우
   => 이 경우에는 값이 0 이다.
2. x수열의 i번째 문자와 y수열의 j번째 문자가 같은 경우
   => 이 경우에는 이전 단계(x수열의 i-1번째, y수열의 j-1번째까지의 비교)에서의 값 +1 이다.
3. x수열의 i번재 문자와 y수열의 j번째 문자가 다른 경우
   => 이 경우에는 x수열의 i번째와 y수열의 j-1번째, x수열의 i-1번째와 y수열의 j번째와 비교해서 최댓값 취한다.

 

문제 풀이 코드

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

public class _9251_LCS {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		char[] s1 = in.readLine().toCharArray();
		char[] s2 = in.readLine().toCharArray();
		int[][] lcs = new int[s1.length+1][s2.length+1];
		for(int i = 1; i<= s1.length;++i) {
			for(int j = 1; j<=s2.length;++j) {
				if(s1[i-1] == s2[j-1]) {
					//이번 문자가 같을 경우, 이전 경우의 수 +1
					lcs[i][j] = lcs[i-1][j-1]+1;
				}
				else {
					//이번 문자가 다를 경우, s1수열의 이전값과 s2수열의 이전 값 비교
					lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
				}
			}
		}
		System.out.println(lcs[s1.length][s2.length]);
	}
}