[백준_9251번] LCS

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

9251번: LCS

[문제]

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

 

[입력 조건]

 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

[코드]

import java.util.*;

public class BaekJoon_9251 {
	static char[] str1;
	static char[] str2;
	
	// dp에는 각 수열의 부분 수열을 늘려가며 찾은 부분 수열 길이의 누적 합이 저장되어 있다.
	static Integer[][] dp; 
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		// toCharArray() : 문자열을 char[] 배열로 반환해주는 메소드
		str1=sc.nextLine().toCharArray();
		str2=sc.nextLine().toCharArray();
		
		dp=new Integer[str1.length][str2.length];
		
		System.out.println(LCS(str1.length-1,str2.length-1));
	}
	
	/*
	 * LCS : Longest Common Subsequance(긴 공통된 부분수열)
	 * 임의의 두 수열에서 각각의 부분수열 중 서로 같은 부분 수열 중에서 가장 긴 부분 수열을 의미한다.
	 * 
	 * x번째 원소와 y번째 원소가 같다면 (x-1,y-1)의 LCS 길이의 +1이 된다.
	 * 같지 않다면 LCS(x-1,y)와 LCS(x,y-1) 중 큰 값을 갖는다. 
	 */
	public static int LCS(int x, int y) {
		// 인덱스 밖 (공집합)일 경우 0 반환
		if(x==-1||y==-1)
			return 0;
		
		if(dp[x][y]==null) {
			dp[x][y]=0;
			
			// str1의 x번째 문자와 str2의 y번째 문자가 같은지 검사
			if(str1[x]==str2[y])
				dp[x][y]=LCS(x-1,y-1)+1;
			// 같지 않다면 LCS(dp)[x-1][y]와 LCS(dp)[x,y-1] 중 큰 값으로 초기화
			else 
				dp[x][y]=Math.max(LCS(x-1,y),LCS(x,y-1));
		}
		return dp[x][y];
	}
}

 

[고찰]

 이번 문제는 앞선 LIS와 비슷한 유형이지만 어떻게 접근해야 하는지 몰라 다른 사람의 포스팅을 참고하여 해결하였다. 해당 문제를 해결하기 위해서는 두 수열의 부분 수열을 늘려가며 부분 수열의 길이 누적 합을 2차원 배열 dp에 저장해야 한다. 표를 만들어가며 규칙성을 찾으려 노력했지만 보이지 않아 어떻게 답을 도출해야 할지 몰랐는데 다른 사람의 포스팅을 보며 이해하였다.

 막상 정답을 보면서도 이러한 규칙이 있다는 것을 발견하기 어려웠는데 스스로 해결할 수 있도록 여러번의 복습이 필요하다고 생각한다. 

 

[참고]

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전