[백준] 9251, LCS(Longest Common Subsequence)

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

[9251번: LCS

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

www.acmicpc.net](https://www.acmicpc.net/problem/9251)

문제해결과정

최장 공통 부분 수열

2개의 문자열이 주어지고 두 문자열의 공통 부분 문자열 중, 가장 긴 것의 길이를 구하는 문제.

각 문자열의 i번째, j번째 문자를 포함을 시키거나 포함하지 않는 공통 부분 문자열의 길이를 구한다.

 

유명한 dp문제이다.

dp테이블은 dp[i][j] => LCS(str1(0...i), str2(0...j)]로 정의한다.

- str1 의 i번째 문자와 str2의 j번째 문자가 같다면 각 문자열의 마지막 index 원소를 포함시키는 subsequence가 생기므로
    ->dp[i][j] = dp[i-1][j-1] + 1
- str1 의 i번째 문자와 str2의 j번째 문자가 같지 않다면
    -> dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

dp 문제를 해결할 때, 문제에 따라서 모든 작은 문제가 독립적일 필요는 없다.

작은 부분 문제가 서로 겹치거나 중복이 발생하는 경우가 있더라도 (주로 최대, 최소를 구하는 문제) 메모이제이션을 활용하고 시간복잡도 측면에서 문제가 발생하지 않는다면 충분히 활용가능하다.

import java.io.*;
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();

        int ans = solve(s1, s2);
        System.out.println(ans);
    }
    
    static int solve(String s1, String s2){
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for(int i = 1; i <= s1.length(); i++){
            for(int j = 1; j <= s2.length(); j++){
                //a, b의 마지막 문자 활용
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                //a의 마지막 문자 활용 x
                //b의 마지막 문자 활용 x
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[s1.length()][s2.length()];
    }
}