백준 9251 - LCS Java

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

9251번: LCS

문제

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

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

입력

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

출력

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

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

 

문제 풀이

DP의 유명한 유형인 LCS를 활용하는 문제이다.

LCS는 두 수열이 주어졌을 때 두 수열 모드의 부분 수열이 되는 수열 중 가장 긴 것. 이라고 문제에 나와 있듯이. 이를 해결하여 풀면 된다.

dp 테이블은 2차원 배열로 정의하고, 각 문자열의 길이만큼의 크기로 정의한다.

각 배열의 요소를 탐색하며, 현재 인덱스의 문자가 가리키는 문자와 일치할 경우

dp[i][j] = dp[i-1][j-1] + 1  점화식을 통해, 기존에 탐색하며 찾았던 수열의 길이에 +1을 해준다.

만약 문자가 일치하지 않을 경우에는

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) 점화식을 통해, 기존에 탐색하며 찾았던 값들을 비교하여 그 중 큰 값을 저장한다.

예를 들어, 문자열 A : "ACAYKP"와 문자열 B : "CAPCAK"가 주어졌을 경우,

i는 문자열 A의 C를 가리키고, 

j는 문자열 B의 A를 가리킨다고 했을 때, 두 개의 문자가 다르기 때문에

dp[i-1][j] 는 문자열 B가 가리키는 값인 A에서 -1을 하여 문자열 A의 C와 문자열 B의 C를 가지고 탐색한 값

dp[i][j-1] 는 문자열 A가 가리키는 값인 C에서 -1을 하여 문자열 A의 A와 문자열 B의 A를 가지고 탐색한 값

둘 중 큰 값을 가지고 dp 테이블에 저장한다.

 

코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_9252_LCS {
    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 alength = a.length();
        int blength = b.length();
        char[] A = new char[alength+1];
        char[] B = new char[blength+1];
        int[][] dp = new int[blength+1][alength+1];

        for(int i=1; i<=alength; i++)
        {
            A[i] = a.charAt(i-1);
        }
        for(int i=1; i<=blength; i++)
        {
            B[i] = b.charAt(i-1);
        }
        for(int i=1; i<= blength; i++)
        {
            for(int j=1; j<= alength; j++)
            {
                if(B[i] == A[j])
                {
                    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[blength][alength]);

    }
}