[백준] 9251번 : LCS (JAVA)

인간몽쉘김통통·2024년 1월 17일

LCS 다이나믹 프로그래밍 백준 알고리즘

백준

목록 보기

53/92

문제

이해

LCS는 최장 공통 부분 수열의 약자이다. 다시 말해 두 수열이 주어졌을 때 양쪽의 공통 부분 수열 중에서 가장 긴 것을 찾으면 된다.

가장 긴 LCS의 길이를 출력하자.

접근

LCS 문제는 따로 위키백과에 있을 정도로 유명한 문제인 것 같다.

처음에 문제를 봤을 때 전혀 감이 잡히질 않았다. 생각해봤던 것은 어찌됐든 길이가 길어지면 그만큼 LCS도 커질 수 있으니 DP 문제라는 것을 짐작했다.

개인적으로 어떻게 DP를 세워야할 지 모르겠어서 다른 사람의 풀이와 위키백과를 참조했다.

결론적으로 DP를 2차원 배열로 두고 각각의 인덱스를 문자열의 길이로 취급하고 타뷸레이션 혹은 메모이제이션을 활용해서 구하면 되는 것이었다.

문제가 어렵다고 생각되는 것이 위와 같이 DP를 2차원 배열로 생각하고 DP 테이블을 작성해도 규칙을 발견하지 못하면 풀기 어려워 보였기 때문이다.

아래는 예제에 대한 DP 테이블이다.

예로 (C, A)는 수열 {C} 와 {A}의 LCS를 의미하고 (P, Y)는 {C,A,P}와 {A,C,A,Y}의 LCS를 의미한다.

테이블을 보면 규칙을 발견할 수 있다. 바로 행과 열의 끝이 같은 값일 때 LCS가 1씩 커진다는 것이다.

어떻게 보면 당연한 얘기이다. 공통된 끝 값 오기 전의 LCS는 당연히 1보다 작기 때문이다. 같은 값이 뒤로 붙음으로써 LCS가 1씩 커지게 되는 것이다.

그렇다면 같은 값이 오지 않을 때는 어떻게 변화하는지 확인해보자. 우리가 테이블을 채울 때 행과 열을 기준으로 채우게 되는데 이 때 같은 값이 아니라면 공통된 부분이 없기 때문에 이전 값을 그대로 가져가면 된다.

예로 마지막 좌표인 (K, P)를 보면 열을 기준으로는 증가했지만 행을 기준으로는 그대로 4가 온다. 이 때는 행과 열에 대하여 이전 값을 각각 비교하여 큰 값을 선택하면 된다.

여기까지 정리한 점화식은 다음과 같다.
DP[N][M] = DP[N-1][M-1] + 1 (Xi == Yi)
= Max(DP[N-1][M], DP[N][M-1]) (Xi != Yi)

이상으로 코드를 작성해보자.

코드

package java_baekjoon;

import java.io.*;
import java.util.*;

public class prob9251 {
  static String l;
  static String r;
  static int[][] dp;

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

    l = br.readLine();
    r = br.readLine();

    dp = new int[l.length() + 1][r.length() + 1];
    dp[1][1] = l.charAt(0) == r.charAt(0) ? 1 : 0;

    for (int i = 0; i < l.length(); i++) {
      for (int j = 0; j < r.length(); j++) {
        if (i == 0 && j == 0) {
          continue;
        }

        if (l.charAt(i) == r.charAt(j)) {
          dp[i + 1][j + 1] = dp[i][j] + 1;
        } else {
          dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
        }
      }
    }

    System.out.println(dp[l.length()][r.length()]);
  }

}