[백준] 9251번 LCS

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 길이를 구하는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 유효하며 4를 답으로 출력한다.

   첫째 줄과 둘째 줄에 두 문자열이 주어진다. 제한 사항은 다음과 같다.

 

• 1 ≤ 문자열 길이 ≤ 1000
• A ≤ 문자 ≤ Z

 

 

---

접근 방식

   DP의 개념을 이용해 문제를 해결하였다. 배열의 행과 열은 각각 입력받은 문자열을 의미하며 배열의 값은 들어온 문자열들로 만들 수 있는 수열 중 최대 길이를 나타낸다. (행과 열의 각 0번째 인덱스는 아무것도 안들어온 경우를 의미한다.) 다음 예제를 보자.

 

 

   먼저 1행은 문자열 "C"가 들어왔을 때, 문자열 "ACAYKP"와 만들 수 있는 부분 수열의 최대 길이를 의미한다. (1, 1) 좌표는 문자열 "A"와 문자열 "C"가 있을 때 만들 수 있는 최대 길이지만 지금 상태론 아무것도 만들 수 없기 때문에 0으로 초기화한다.

 

 

   다음 (1, 2) 좌표는 문자열 "AC"와 문자열 "C"가 있을 때 만들 수 있는 최대 길이를 의미한다. 이 경우 "C"라는 부분 수열을 구할 수 있기 때문에 1로 초기화한다.

 

 

   다음 (1, 3) 좌표는 문자열 "ACA"와 문자열 "C"가 있을 때 만들 수 있는 최대 길이를 의미한다. 이 경우에도 "C"라는 부분 수열을 구할 수 있기 때문에 1로 초기화할 수 있다. 이와 같은 방식으로 1행의 과정을 마무리해보자.

 

 

   이번엔 2행의 과정을 알아보자. (2, 1) 좌표는 문자열 "A"와 문자열 "CA"가 있을 때 만들 수 있는 최대 길이를 의미한다. 이 경우 "A"라는 부분 수열을 구할 수 있기 때문에 1로 초기화할 수 있다.

 

 

   이와 같은 방식으로 2행도 똑같이 채우면 다음과 같다.

 

 

   채워진 2행을 잘 살펴보자. (2, 2) 좌표의 경우 문자열 "AC"와 문자열 "CA"가 들어온 경우이다. 유효한 부분 수열은 "C"와 "A"가 존재하며 최대 길이는 1임을 알 수 있다. (2, 3) 좌표는 "CA"라는 유효한 부분 수열이 존재하므로 최대 길이는 2로 초기화된다.

 

 

   이제 규칙을 추론해보자. (2, 3) 좌표의 특징은 행과 열에서 들어온 문자가 같다는 것이다. 이 말의 의미는 현재 들어온 문자들("A", "A")을 제외하고 이전까지 들어온 문자열들("AC", "C")로 만들수 있는 유효한 부분 수열의 최대 길이보다 더 큰 부분 수열을 만들 수 있다는 것이다. 즉, (2, 3)의 좌표는 (1, 2) 좌표의 값보다 1 더 큰 값을 갖고 dp[2][3] = dp[1][2] + 1이라는 식을 얻을 수 있다.

 

 

   이번엔 행과 열에서 들어온 문자가 다른 경우를 살펴보자. (2, 4) 좌표는 문자 "Y"와 "A"가 들어온 경우이다. 이 경우 유효한 부분 수열들은 문자열 "ACAY"와 문자열 "CA"로 만들 수 있는 경우이다. 좀 더 세부적으로 나누면 문자열 "ACAY"와 문자열 "C"로 만들 수 있는 경우와 문자열 "ACA"와 문자열 "CA"로 만들 수 있는 경우이다. 즉, 우리는 (1, 4) 좌표와 (2, 3) 좌표의 값 중에서 더 큰 값으로 현재 좌표의 값을 초기화하면 되고 dp[2][4] = Math.max(dp[2][3], dp[1][4])라는 식을 얻을 수 있다.

 

 

   3행의 경우에도 같은 조건으로 채워지는 것을 확인할 수 있으며, 만들어진 두 식을 이용해 일반화하면 다음과 같은 점화식을 얻을 수 있다.

 

• 행과 열의 문자가 같은 경우 : dp[i][j] = dp[i - 1][j - 1] + 1
• 행과 열의 문자가 다른 경우 : dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])

---

코드

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

public class 백준9251번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        char[] strA = br.readLine().toCharArray();
        char[] strB = br.readLine().toCharArray();
        int[][] dp = new int[strA.length + 1][strB.length + 1];

        for (int i = 1; i <= strA.length; i++) {
            for (int j = 1; j <= strB.length; j++) {
                if (strA[i - 1] == strB[j - 1]) {
                    //현재 문자를 제외하고 이전까지 만들어진 경우 중에서 max값 + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //현재 문자를 포함하고 이전까지 만들어진 경우 중에서 max값
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        System.out.println(dp[strA.length][strB.length]);
    }
}