[백준 9251][DP] LCS

 

 

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

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

 

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

 

 

 

 

점화식 

• dp[i][j]: 수열1 i까지, 그리고 수열 j 까지 최장 공통 부분 수열 길이 

 

 

• 수열 ACAYKP, CAPCAK에 대해 점화식을 2차원 배열로 표현하면 다음과 같다. 
• 원소 하나에 대해 3가지 방향으로부터 영향을 받아 값이 정해진다. 

 

특징

• LCS 기본 문제 
• 점화식 루프를 돌때 배열의 범위를 벗어나지 않게 조심해야 한다. 
• 따라서 i 또는 j가 0인 경우는 따로 로직으로 처리해줄 수 있다.

 

 

 

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Baek9251_3 {
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        char[] arr1 = br.readLine().toCharArray();
        char[] arr2 = br.readLine().toCharArray();
 
        int len = Math.max(arr1.length, arr2.length);
        int[][] dp = new int[len][len];
 
        // 가장 처음 문자가 같은 경우 1을 세준다.
        if(arr1[0] == arr2[0]) {
            dp[0][0] = 1;
        }
 
        // arr2가 0번째 인경우 공식 처리
        for (int i = 1; i < arr1.length; i++) {
            if (arr1[i] == arr2[0]) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = dp[i-1][0];
            }
        }
 
        // arr1이 0번째 인경우 공식 처리
        for (int i = 1; i < arr2.length; i++) {
            if (arr1[0] == arr2[i]) {
                dp[0][i] = 1;
            } else {
                dp[0][i] = dp[0][i-1];
            }
        }
 
        // arr1, arr2 각각 1부터 마지막까지 순환식 풀기
        for (int i = 1; i < arr1.length; i++) {
            for (int j = 1; j < arr2.length; j++) {
                if (arr1[i] == arr2[j]) {
                    dp[i][j] = Math.max(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[arr1.length - 1][arr2.length - 1]);
    }
}