[BOJ] 백준 9251번 LCS (Java)

#9251 LCS

난이도 : 골드 5

유형 : DP

9251번: LCS

▸ 문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

▸ 입력

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

▸ 출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

문제 풀이 

처음에는 이중 포문으로 그냥 돌리면 되는 문제인 줄 알았지만 쉽게 풀리지 않았다. DP 이차원배열을 사용해야 했다. LCS는 최장 공통 부분 수열로 연속되지 않아도 되는 것을 알아야 한다.

 

예를 들어, ACAYKP 와 CAPCAK의 LCS를 찾아보면

ACAYKP

CAPCAK

-> ACAK가 LCS가 된다. 

 

• i : str1의 문자열 i번째 문자, j : str2의 문자열 j번째 문자

1) if(i==j) 만약 i와 j가 같다면,  str1(0~i-1)과 str2(0~j-1)의 LCS + 1을 해준다.

 (ex. ACAYKP

       CAPCAK

    i=3, j=2 일 때,  (AC C 의 LCS : dp[2][1] =1 ) + 1  = 2)

 

2) if(i!=j) i와 j가 다르다면,

str1(0~i-1)과 str2(0~j)의 dp[i-1][j],

str1(0~i)와 str2(0~j)의 dp[i][j-1] 중 최댓값을 받아온다.

 (ex. ACAYKP

        CAPCAK

    i=3, j=3 일 때,  (AC CAP의 LCS : dp[2][3] =1 )  vs (ACA CA dp[3][2] =2 ) -> 2 )

 

2차원 배열 dp를 표로 나타내면 다음과 같다. 

i   \   j	0	C 1	A 2	P 3	C 4	A 5	K 6
0	0	0	0	0	0	0	0
A 1	0	0	1	1	1	1	1
C 2	0	1	1	1	2	2	2
A 3	0	1	2	2	2	3	3
Y 4	0	1	2	2	2	3	3
K 5	0	1	2	2	2	3	4
P 6	0	1	2	3	3	3	4

 

풀이 코드 

import java.io.*;

public class Main {

	static int[][] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		String str2 = br.readLine();
		
		System.out.println(LCS(str1, str2));
		
	}
	
	static int LCS(String str1, String str2) {
		int n1 = str1.length();
		int n2 = str2.length();
		
		dp = new int[n1+1][n2+1];
		
		for(int i=1; i<n1+1; i++) {
			for(int j=1; j<n2+1; j++) {
				if(str1.charAt(i-1) == str2.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]);
				}
			}
		}
		
		return dp[n1][n2];
	}
}