[백준/자바] 9251번: LCS

문제

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

풀이

• 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것의 길이를 출력
  • 부분 수열이란, 문자열에서 일부 문자를 선택해 순서를 유지하면서 만든 수열

ex) "ACAYKP", "CAPCAK"
공통 부분 수열: "ACAK" (길이 4)

단순히 모든 부분 수열을 만들어 비교하면 경우의 수가 너무 많아지므로, DP 사용

첫 번째 문자열의 처음 i개 문자, 두 번째 문자열의 j개 문자까지 고려했을 때 LCS 길이를 비교하며 더해가면 됩니다.

        // 2중 for문으로 DP 테이블 채우기
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                // 현재 문자가 같으면 → 대각선 값 + 1
                if (str1.charAt(i-1) == str2.charAt(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]);
                }
            }
        }

• str1[i-1] == str2[j-1]
  • 마지막 문자가 서로 같다면, 그 문자를 LCS에 포함
  • 포함했다면 두 문자열 모두에서 그 문자를 소비했으니, 둘 다 한 칸씩 줄인 것이 됨
• str1[i-1] != str2[j-1]
  • 마지막 문자가 서로 다르다면, 방금 문자는 둘 다 동시에 LCS의 마지막이 될 수 없다.
  • 최적해는 "둘 중 하나는 버린 경우"에서 나옴
  • dp[i-1][j]: str1의 마지막 문자를 버리고 비교
  • dp[i][j-1]: str2의 마지막 문자를 버리고 비교
  • 둘 다 시도해 보고 더 긴 쪽을 택하면 됩니다.

간단한 예시로 보여드리겠습니다.

str1 = "ABC", str2 = "BAC"

0. 초기 상태 (모두 0)

i\j	0	1(B)	2(A)	3(C)
0	0	0	0	0
1(A)	0	0	0	0
2(B)	0	0	0	0
3(C)	0	0	0	0

1. i=1 (A)

• j=1(B): 다름 → max(위=0, 왼쪽=0) = 0
• j=2(A): 같음 → 대각선(0)+1 = 1
• j=3(C): 다름 → max(위=0, 왼쪽=1) = 1

i\j	0	1(B)	2(A)	3(C)
0	0	0	0	0
1(A)	0	0	1	1
2(B)	0	0	0	0
3(C)	0	0	0	0

2. i=2 (B)

• j=1(B): 같음 → 대각선(0)+1 = 1
• j=2(A): 다름 → max(위=1, 왼쪽=1) = 1
• j=3(C): 다름 → max(위=1, 왼쪽=1) = 1

i\j	0	1(B)	2(A)	3(C)
0	0	0	0	0
1(A)	0	0	1	1
2(B)	0	1	1	1
3(C)	0	0	0	0

3. i=3 (C)

• j=1(B): 다름 → max(위=1, 왼쪽=0) = 1
• j=2(A): 다름 → max(위=1, 왼쪽=1) = 1
• j=3(C): 같음 → 대각선(1)+1 = 2

i\j	0	1(B)	2(A)	3(C)
0	0	0	0	0
1(A)	0	0	1	1
2(B)	0	1	1	1
3(C)	0	1	1	2

결과는 dp[3][3] = 2
AC나 BC가 되므로 최대 2가 됩니다.

코드

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

public class Main {
	static String str1, str2;
	static int[][] dp;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str1 = br.readLine();
		str2 = br.readLine();
		
		dp = 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.charAt(i-1) == str2.charAt(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.println(dp[str1.length()][str2.length()]);
	}
}