[백준] 9251_LCS / 최장 공통 부분 수열, 동적계획법, DP

 

 

Gold

 

 

문제

 

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

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

 

 

입력

 

첫째 줄과 둘째 줄에 두 문자열이 주어진다.

문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

 

출력

 

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

 

 

---

 

풀이

 

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

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        String A = sc.nextLine();
        String B = sc.nextLine();
        
        // A.length(), B.length()만큼 모두 탐색하기 위해 초기화 
        int[][] dp = new int[A.length()+1][B.length()+1];

        for(int i=1; i<=A.length(); i++){
            for(int j=1; j<=B.length(); j++){
                if(A.charAt(i-1) == B.charAt(j-1)){ 
                    // 두 문자가 같을 경우 LCS 업데이트
                    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[A.length()][B.length()]);
        br.close();
    }
}

 

 

 

해결 방법

• A, B 두 문자열을 모두 탐색하기 위해 dp 배열의 크기를 [A.length() + 1][B.length() + 1]로 세팅
• dp[i][j] = A의 처음 i개의 문자와  B의 처음 j개의 문자의 최장 공통부분 수열 LCS의 길이를 저장
• db배열을 업데이트
  1. 비교하는 두 문자가 같을 때 LCS를 업데이트
     -> 직전 LCS + 1 -> dp[i][j]=dp[i−1][j−1]+1 
  2. 비교하는 두 문자가 다를 때 이전 LCS 중 최장 길이로 업데이트한다.
     -> A.charAt(i-1)을 포함하지 않는 경우, B.charAt(j-1)을 포함하지 않는 경우 중 큰 값 (현재 문자를 추가할 수 없으므로 두 경우를 사용)
     -> Math.max(dp[i-1][j], dp[i][j-1]);
•  dp[A.length()][B.length()]에 최장 공통부분 수열의 길이가 저장된다. 

 

 

 

 

 

 

---

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