[Baekjoon] LCS - Java

문제

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

 

풀이

두 문자열이 주어졌을 때, 두 문자열의 공통 부분 수열의 최대 길이를 구하는 문제이다.

 

ACAK

CBAK

위 두 문자열이 있다고 하자.

 

그러면 부분 수열은 CAK가 부분 수열이 될 것이다.

 

이 문제를 잘보면,

ACAK와 C의 공통 부분 수열의 길이를 구한다.

ACAK와 CB의 공통 부분 수열의 길이를 구한다.

ACAK와 CBA의 공통 부분 수열의 길이를 구한다.

ACAK와 CBAK의 공통 부분 수열의 길이를 구한다.(목표 == 우리가 원하는 것)

 

문자열을 하나씩 붙이면서 큰 문제 즉, 우리가 원하는 문제를 만들고 있다.

작은 문제에서 큰 문제를 구할 때 사용하는 알고리즘은 다이나믹 프로그래밍을 이용하면 된다.

 

1. 테이블을 정의한다.

dp[i][j] = 문자열 s1에서 i - 1번째 까지의 부분 수열과 문자열 s2에서의 j - 1번째까지의 부분 수열에서 가지는 최대 길이

 

2. 우리가 원하는 답을 테이블에서 구할 수 있는지 확인한다.

dp[s1의 길이][s2의 길이] = 우리가 원하는 답을 구할 수 있다.

 

3. 정의한 테이블로 초기화를 어떻게 하면 될지 생각한다.

테이블을 초기화할 필요가 없다. 

 

4. 점화식을 구성해본다.

	C	B	A	K
A	0	0	1	1
C	1	1	1	1
A	1	1	2	2
K	1	1	2	3

 

위 테이블을 보자. 

arr[i] != arr[j]일 경우

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])이다.

i번째가 없을 경우의 공통 부분 수열의 최대 길이 vs j번째가 없을 경우의 공통 부분의 최대 길이 이 두가지를 비교한 최댓값이 된다.(두 문자가 다르기 때문에, 부분 수열의 길이가 늘어나지 않기 때문이다.)

 

arr[i] == arr[j]일 경우

dp[i][j] = dp[i - 1][j - 1] + 1이다. 

문자가 같기 때문에, 공통 부분 수열의 길이가 늘어나야한다.

문자를 무조건 포함할 것이기 때문에 dp[i - 1][j - 1] = 같은 문자를 포함하지 않았을 때의 최대 길이에서 1을 더하면 된다.

 

소스코드

import java.io.*;

public class Main {
    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[][] dp = new int[arr1.length + 1][arr2.length + 1];

        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                if (arr1[i - 1] == arr2[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.print(dp[arr1.length][arr2.length]);

        br.close();
    }
}

 

실행결과