개발 블로그

접근 방법

처음에는 완전 탐색으로 해결하려고 했다. 그러나 해당 문제의 제한 시간은 0.1초라 dp로 해결해야함을 알게 되었다.

최장 공통 수열을 찾기 위해서는 마지막의 문자에 주목해야한다. 

ABDE와 ABE의 공통 수열을 찾는다고 해보자. 주어진 문자열은 길이가 짧아서 바로 LCS = "ABE"라는 답이 나오지만, 

문자열이 길어지면 한 눈에 파악하기 어렵다. 그럴 때는 마지막부터 거꾸로 거슬러 올라갈 수 있다.

즉, 마지막 문자열인 E가 동일하니, ABD와 AB의 LCS에 +1을 더하면 그것이 답이 되는 것이다. (arr[i-1][j-1] + 1)

그러나 이 로직은 마지막 문자가 서로 같을 경우에만 적용되며, ABD와 AB처럼 서로 다른 경우에는 아래와 같이 경우를 나눠서 생각해야 한다.

1)  D를 포함시킬 때 : ABD - A 간의 LCS = 1(A)    (arr[i-1][j])

2) B를 포함시킬 때 : AB - AB 간의 LCS = 2(AB)  (arr[i][j-1])
서로 다른 끝 문자를 하나씩 포함시킬 때, 둘 중 LCS의 최대값이 ABD와 AB의 LCS가 된다. Max(arr[i-1][j], arr[i-1][j])

이를 코드로 작성하면 아래와 같다. 

import java.util.*;
public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String strA = sc.nextLine();
        String strB = sc.nextLine();

        int arr[][] = new int[1001][1001];

        for(int i = 1; i<=strB.length(); i++){
            for(int j = 1; j<=strA.length(); j++){
                if(strB.charAt(i-1) == strA.charAt(j-1)){	//끝 문자가 같을 때 
                    //arr[i][j] = arr[i-1][j] + 1;
                    arr[i][j] = arr[i-1][j-1] + 1;
                }
                else{										//끝 문자가 다를 때
                    //arr[i][j] = arr[i][j-1];
                    arr[i][j] = Math.max(arr[i][j-1], arr[i-1][j]);	
                }
            }

        }
        System.out.println(arr[strB.length()][strA.length()]);
    }
}