[JAVA] 백준 9251번 - LCS

 

📖 문제

 

📋 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		
		String s1 = sc.nextLine();
		String s2 = sc.nextLine();
		int row = s1.length();
		int column = s2.length();
		
		int dp[][] = new int[row+1][column+1];
		
		for (int i = 1; i <= row; i++) {
			for (int j = 1; j <= column; j++) {
				if(s1.charAt(i-1) == s2.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]);
				}
			}
		}
		
		System.out.println(dp[row][column]);
		
//		for (int i = 1; i <= row; i++) {
//			for (int j = 1; j <= column; j++) {
//				System.out.print(dp[i][j]+" ");
//			}
//			System.out.println();
//		}
		
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

예제 입력 > ACAYKP CAPCAK

s1 : ACAYKP 
s2 : CAPCAK

dp[i][j] : s1의 0~i번째까지의 부분 문자열과 s2의 0~j번째까지의 부분 문자열의 LCS

예를 들어 dp[3][2]의 경우에는 'ACA'과 'CA'의 LCS의 길이 값을 저장하게 됩니다.

 

dp값을 구하면서 각각 2가지의 경우의 수가 나오게 되는데,

1. s1[i] == s2[j] 인 경우

두 문자가 같기 때문에 확정적으로 LCS의 마지막 부분이 완성되게 됩니다. 따라서
dp[i][j] = dp[i-1][j-1]+1

예를 들어 dp[2][4]를 구해야 한다고 생각해봅시다.
'AC'와 'CAPC'의 LCS를 구해야 하는데 마지막 부분이 s1[i] = C, s2[j] = C로 같습니다.
따라서 LCS의 마지막 부분은 'C'가 되는 것이고
마지막 부분을 제외한 'A'와 'CAP'의 LCS를 구해서
거기에 +1을 해주면 'AC'와 'CAPC'의 LCS를 구할 수 있게 됩니다.

dp특성상 이미 'A'와 'CAP'의 LCS값인 dp[1][3]을 구해놨기 때문에
dp[2][4] = dp[2-1][4-1] + 1 = dp[1][3] + 1 = 2입니다.

 

2. s1[i] != s2[j] 인 경우

dp[3][3]의 경우를 예시로 들어보겠습니다.

dp[3][3]은 'ACA'와 'CAP'의 LCS길이인데 마지막 문자가 똑같지 않으므로
'AC'와 'CAP'의 LCS와 'ACA'와 'CA'의 LCS를 비교해서 큰 값이 'ACA'와 'CAP'의 LCS가 됩니다.
따라서 dp[3][3] = max(dp[2][3], dp[3][2]) 라는 식이 나오게 됩니다.

 

 

🔗 링크

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

9251번: LCS