[BOJ] 9251 LCS - JAVA

1. 문제

9251번: LCS

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

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

---

2. 풀이

DP로 풀었는데, 규칙은 다음과 같다.

1) 글자가 같으면 이전글자([i-1][j-1])에서 +1을 한다.

2) 같지 않다면 이전([i-1][j], [i][j-1])부분과 비교해서 더 큰 값을 저장한다. 연속된 수열이 아니라 최장 공통부분을 찾는 것이기 때문이다.

 ACAYKP와 CAPCAK의 LCS를 찾는 것을 예시로 들면 dp는 이렇게 완성된다. 파란색 부분으로 칠해진 칸이 글자가 같은 경우다. 이때는 빨간색 화살표처럼 이전 값에서 +1을 하고, 그 외의 경우는 파란색 화살표처럼 위, 오른쪽에서 더 큰 값을 저장한다.

import java.io.*;

public class BOJ_9251_LCS {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      char[] str1 = in.readLine().toCharArray();
      char[] str2 = in.readLine().toCharArray();

      int[][] lcs = new int[str1.length+1][str2.length+1];
      for(int i=1;i<=str1.length;i++){
         for(int j=1;j<=str2.length;j++){
            if(str1[i-1]==str2[j-1]) lcs[i][j] = lcs[i-1][j-1]+1;
            else lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
         }
      }

      System.out.println(lcs[str1.length][str2.length]);
   }
}

---

3. 결과