LCS

문제 정보

• 백준 골드 4
• DP
• 문제 링크

풀이

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

LCS를 구하려면 두 문자열을 동시에 고려해야 한다. 문자열 A의 i번째까지, 문자열 B의 j번째까지 봤을 때의 LCS 길이를 저장하면, 이전 단계의 결과를 재사용할 수 있다. 따라서 dp[i][j]를 다음과 같이 정의한다.

• dp[i][j]: 문자열 A의 i번째 글자와 문자열 B의 j번째 글자까지의 LCS 길이

dp[i][j]를 구할 때 A[i]와 B[j]가 같은지 여부로 경우를 나눈다.

1. A[i] == B[j]인 경우
   • 두 문자가 같으므로 이 문자를 LCS의 마지막 원소로 사용할 수 있다. A의 i번째와 B의 j번째를 제외한 상태, 즉 dp[i-1][j-1]의 LCS에 현재 문자를 하나 추가하면 된다.
   • → dp[i][j] = dp[i-1][j-1] + 1
2. A[i] != B[j]인 경우
   • 두 문자가 다르므로 현재 문자를 LCS에 추가할 수 없다. 이 경우 다음 두 가지 중 더 긴 것을 선택한다.
     • A의 i번째 문자를 제외한 경우: dp[i-1][j]
     • B의 j번째 문자를 제외한 경우: dp[i][j-1]
   • → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

코드

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String A = br.readLine();
        String B = br.readLine();
        
        int n = A.length();
        int m = B.length();
        
        int[][] dp = new int[n + 1][m + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.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[n][m]);
    }
}