Baekjoon | Q.9251 - LCS

9251번: LCS

최장 공통 부분 수열(Longest Common Subsequence, LCS)를 찾는 문제이다. 

 

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str1 = sc.next();
    String str2 = sc.next();
    sc.close();

    int[][] dp = new int[str1.length()][str2.length()];
    
    for (int i = 0; i < dp.length; i++) {
      char c1 = str1.charAt(i);

      for (int j = 0; j < dp[0].length; j++) {
        char c2 = str2.charAt(j);
        
        if(c1 == c2) {
          if(i == 0 || j == 0) {
            dp[i][j] = 1;
          }else {
            dp[i][j] = dp[i-1][j-1] + 1;
          }
        }else {
          if(i == 0) {
            if(j == 0) {
              dp[i][j] = 0;
            }else {
              dp[i][j] = dp[i][j-1];
            }
          }else {
            if(j == 0) {
              dp[i][j] = dp[i-1][j];
            }else {
              dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
          }
        }
      }
    }

    System.out.println(dp[str1.length()-1][str2.length()-1]);
  }
}

 동적 프로그래밍을 이용하여 문제를 해결했다. dp[i][j]는 0~i까지 str1, 0~j까지 str2 에서 LCS의 길이를 의미한다. 

 

 만약 비교하는 문자가 같다면 dp[i][j] = dp[i-1][j-1] + 1이 되고 같지 않다면 dp[i][j]는 dp[i-1][j]와 dp[i][j-1] 중 더 큰값이 된다. 배열에서 인덱스의 범위가 잘못될 경우를 고려하여 i와 j가 0일 경우를 따로 분기해주었다. 구글링을 통해 다른 사람들의 코드를 살펴보니 처음 배열을 잡을 때, 길이보다 +1만큼 배열을 선언해주면 간단하게 해결되는 문제였다..

 

 ACAYKP CAPCAK를 예시로 살펴보자.

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

 

 예시의 두 문자열의 LCS의 길이는 4가 된다.