[99클럽 코테스터디 23일차 TIL / 백준] 9251 - LCS (DP)

99클럽 코테스터디 23일차 TIL
KeyWord : DP

문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

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

---

풀이

DP 문제에 익숙하지 않다면 아이디어를 떠올리는 것이 힘들었을 법한 문제였다.

시간제한이 0.1초이니 완전탐색으로는 절대 불가능해 보인다. 또 그리디로 해결하는 것도 잠깐 고민해보니 불가능할 것 같다. 그래서 DP로 풀 수 있겠구나 싶었던 문제다.

• ACAYKP
• CAPCAK

일단 문제에서 주어지는 예시를 가져와보자.

DP의 핵심은 값의 재사용과 복잡한 문제를 작게 쪼개는 데 있다고 했다. 수열을 앞에서 부터 천천히 쪼개보자.

• A / C → 0
• AC / C → 1
• ACA / C → 1
• ACAY / C → 1
• ACAYK / C → 1
• ACAYKP / C → 1

 

• A / CA → 1
• AC / CA → 1
• ACA / CA → 2
• ACAY / CA → 2
• ACAYK / CA → 2
• ACAYKP / CA → 2

이런 식으로 수열을 쪼개가면서 비교를 할 수 있을 것이다. 보면, 부분수열의 길이가 늘어나도 LCS의 길이는 줄어들지 않는 것을 알 수 있다.

복잡한 문제를 작게 쪼개었다.

 

• ACAY / CAPCA

이 두 부분수열의 LCS는 ACA로 3이다. 여기서 각 수열에 원소를 하나 더 붙여보자.

• ACAYK / CAPCAP

LCS는 ACA 길이는 3이다. 부분 수열의 마지막에 값을 추가한다고 하더라도, LCS의 길이는 증가할 수는 있어도 절대 줄어들지 않는다. 즉, 값을 재사용할 수 있다.

이것을 코드로 나타낸다면 아래와 같다.

DP[1][1] : A / C
DP[2][1] : AC / C
DP[3][1] : ACA / C

이렇게 각 부분 수열끼리만 비교했을 때 LCS의 길이를 반복문을 돌려가며 저장한다.

그리고 DP 배열의 마지막, DP[6][6]에 저장되는 값은 원래 주어진 두 수열의 LCS의 길이가 될 것이다. 이해를 돕기 위해 DP 배열을 시각적으로 만들었다. 앞에서부터 차례차례 따라가면 이해할 수 있을 것이다.

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

(인덱스가 -1이 되는 것을 예외처리하는 것보다는 이렇게 배열의 크기를 하나 더 크게한 후 0으로 채우는 것이 코드로 구현할 때 더 쉽다.)

이제 코드로 구현하는 것만 남았다.

 

코드

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

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

        String str1 = br.readLine();  
        String str2 = br.readLine();  

        int[][] dp = new int[str1.length() + 1][str2.length() + 1];  

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

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