백준 | 9251번. 최장 공통 부분 수열(LCS) 찾기 - DP 문풀

⬛ 백준 9251번. 최장 공통 부분 수열(LCS) 찾기 - DP 문풀

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

9251번: LCS

문제

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

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

입력

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

출력

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

---

💚 문제 접근 방식

유명한 문제다. 제대로 이해하고 풀어야 한다.LCS를 더 상세하게 정리한 내용은 여기있다.

DP 알고리즘 | LCS (최장 길이 공통 부분 수열)

---

• D[i][j] 에 대한 정의 : 각 위치 인덱스 i,j를 마지막 문자로 하는 두 문자열의 최장 공통열 길이
• D[i][j]의 점화식

1) A[i] == B[j] 같은 경우 
   D[i][j] = D[i-1][j-1] + 1 

2) A[i] != B[j] 다른 경우 
	 D[i][j] = D[i-1][j] vs D[i][j-1] 중 더 큰 값 세팅 

풀이 설명

---

💚 제출 코드

import java.util.Scanner;

/**
 * 9252번. LCS 2 - DP 문풀 
 * 
 * @author MYLG
 *
 */
public class Main {
	static char[] A;
	static char[] B;
	static int[][] DP;
	/**
	 * DP[i][j] 정의 : A[1~i]와 B[1~j]까지의 LCS 길이
	 * 점화식 
	 * 1) A[i] = B[j] : 직전값에 포함시켜야 하므로 D{i-1][j-1] + 1
	 * 1) A[i] != B[j] : 왼쪽, 위쪾 중 큰 값 (왜냐면, 둘 중 하나가 빠진 거 중에서)더 큰 값으로 이어붙여서 추후에 LCS 만들어야 하니까 
	 */

	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		A = kb.next().toCharArray();
		B = kb.next().toCharArray();
		
		DP = new int[A.length + 1][B.length + 1];
		
		for(int i=1; i<=A.length; i++) {
			for(int j=1; j<=B.length; j++) {
				if(A[i-1] == B[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[A.length][B.length]);
	}

}