9251번 - LCS

1️⃣ DP

 

✏️ 풀이 과정

2차원 DP를 이용해서 수열의 길이를 구할 수 있습니다. 기본적인 아이디어는 LCS를 작은 단위부터 시작해서 만들어갈 수 있다는 것입니다. 가령 ADB와 ACB를 비교한다고 치면 A와 A(1) 다음은 A와 AC(이 때 C와 비교하여 0입니다.) 그리고 A와 ACB(역시 B와 비교하여 0)을 구하는 식으로 A와 B의 모든 자리를 비교해 부분 수열을 만듭니다.(A와 C, A와 B가 아닌 AC와 AB인 이유는 로직 상 만약 왼쪽 A이전에 A가 하나 더 있었다면 AA와 AC를 비교해 길이가 1이 되는 식으로 이전 결과를 고려하기 때문입니다.)  즉 비교하는 알파벳이 같은 경우 이전 결과에 1을 더합니다.

 

다음으로는 AD와 A(D와 A가 다르므로 윗칸의 비교 결과를 가져와 1), AD와 AC(1, D와 C가 다르므로 옆칸의 비교 결과를 가져와 1), AD와 ACB(1, D와 B가 다르므로 옆칸의 비교 결과를 가져와 1)과 같은 결과가 나옵니다. 현재 비교하는 알파벳이 서로 다른 경우는 앞 수열에서 하나를 뺀 경우와 뒤 수열에서 하나를 뺀 경우 중 더 긴 것을 그대로 가져옵니다.(하나 늘어도 그대로일 것이므로)

 

다음으로는 ADB와 A(B와 A가 다르므로 위의 결과를 가져와 1),  ADB와 AC(B와 C가 다르므로 위의 결과를 가져와 1), ADB와 ACB(B와 B가 같으므로 양쪽에서 1씩 뺀 결과에서 1을 더해 2).로 답을 구하게 됩니다.

 

⏱ 시간 복잡도

이차원 배열을 통해 답을 구하기 때문에 시간복잡도는 O(NM) (A길이 * B길이)가 됩니다. 최대 1000글자이므로 1000000정도의 계산량으로 답을 구할 수 있습니다.

 

💻 코드

Java

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 a = br.readLine();
		String b = br.readLine();
		int sizeA = a.length();
		int sizeB = b.length();
		int[][] dp = new int[sizeA+1][sizeB+1];
		for(int i=1;i<=sizeA;i++) {
			for(int j=1;j<=sizeB;j++) {
				if(a.charAt(i-1) == b.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[sizeA][sizeB]);
		br.close();
	}
}