[JAVA] 백준 9251번. LCS (골드5)

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

9251번: LCS

 

안녕하세요!

오늘부터 LCS(최장 공통부분 수열) 문제 3개를 연속으로 풀어보겠습니다!

부분 수열 문제지만 오늘 가져온 9251번 문제처럼 String을 찾는 유형으로도 나오는데요,

0-1 배낭 문제 (Knapsack Problem)과 더불어서 DP의 대표 유형 격인 문제입니다.

그럼 천천히 풀어보겠습니다.

 

 

 

예제를 기준으로 함께 풀어보겠습니다. 

DP의 풀이방법은 정말 다양하고, Dynamic Programming이란 말 그대로 모든 게 가능하기 때문에 딱 잡아 말할 순 없지만, 분할 정복과 유사하게 문제를 잘게 쪼개어 그 결과를 기억하고 이를 통해 답을 만들어낸다고 볼 수 있습니다.

LCS문제도 같습니다.

 

ACAYKP를 String1이라고 하고 이걸 기준으로 놓고 아래의 CAPCAK, String2 의 부분수열을 만들어서 비교해보면,

 

1. C 일때

A-> 0

AC -> 1

ACA-> 1

ACAY ->1

ACAYK ->1

ACAYKP ->1

String2가 C라고 가정했을 때 만들 수 있는 LCS는 길이가 1이라는 사실을 알 수 있습니다.

 

2. CA 일 때

A->1

AC -> 1   (A도 가능하지만 가독성과 이해를 위해 C를 bold 처리했습니다.)

ACA -> 2

ACAY ->2

ACAYK ->2

ACAYKP ->2 String2가 CA일때 만들 수 있는 LCS는 2의 길이라는 사실을 알 수 있습니다.

 

3. CAP 일때

A-> 1

AC -> 1

ACA-> 2

ACAY ->2

ACAYK ->2

ACAYKP ->3

두번째 String이 CAP일 때 LCS는 길이가 3입니다.

슬슬 규칙이 보이시나요? 비교하는 String이 길어질 때,

LCS의 값은 이전에 이 길이까지와 비교한 값과 같거나, 이번에 비교하면서 만들어진 현재의 LCS값이거나,

String1의 이번 Character와 String2에 방금 더해진 문자가 같을 때 1이 커집니다.

 

이걸 코드로 표현해 보면

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


public class Main{
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		int l1 = str1.length();
		String str2 = br.readLine();
		int l2 = str2.length();
		
		int[][] dp = new int[l2+1][l1+1];
		
		for(int i = 1; i <= l2; i++) {
			char C = str2.charAt(i-1);
			for(int j = 1; j <= l1; j++) {
				if(C == str1.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}else {
					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
				}
			}
		}
		System.out.println(dp[l2][l1]);
	}
}

이렇게 나타낼 수 있을것 같네요.

위에서 설명한 것과 같이 String2의 길이를 1씩 늘려가면서 String1과 비교해주고

이번에 비교하는 문자가 같다면 LCS의 값은 이전 비교에서 1만큼 짧았을때의 최댓값 + 1

다르다면 이전 비교에서의 값과 이번 비교에서의 값 중에 큰 값으로 결정됩니다.

 

대부분의 DP문제는 아이디어를 끌어내기가 어렵지, 풀이 방법만 안다면 구현은 쉬운 경우가 많습니다.

DP를 잘 풀기 위해서는 역시 여러 유형을 경험해 익숙해지고 직접 그려가면서 규칙을 찾아내는 방법 뿐 입니다.

이어서 거의 비슷한 문제인 LCS2도 풀어보겠습니다.