[JAVA] 백준 9251 : LCS

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

9251번: LCS

---

문자열이 두 개가 입력이 되었을 때, 각 문자열의 부분수열에 해당하면서 가장 긴 수열을 찾는 문제이다. 

 

ACAYKP
CAPCAK  

이렇게 두개의 문자열이 입력이 되었다면 

두 문자열의 LCS는 ACAYKP , CAPCAK  해서 ACAK이다. 

 

str1을 ACAYKP라고 하고, str1을 기준으로 str2를 비교하여 최대 길이를 알아내야 한다. 

 

1. str1= ACAYKP , str2 = C일 때  부분수열 : C 

A  => 0

AC  => 1

ACA  => 1

ACAY  => 1

ACAYK  => 1

ACAYKP  => 1

 

2. str1= ACAYKP , str2 = CA일때 부분수열 : C, A, CA 

A  => 1

AC  => 1(A 또는 C)

ACA  => 2

ACAY  => 2

ACAYK  => 2

ACAYKP  => 2

 

3. str1= ACAYKP , str2 = CAP일때 부분수열 : C, A, P, CA , CP, AP, CAP

A  => 1

AC  => 1

ACA  => 2

ACAY  => 2

ACAYK  => 2

ACAYKP  => 3

 

이걸 표로 나타내면 아래처럼 나타 낼 수 있다. 

 

 

이걸 바탕으로 규칙을 찾으면 된다. 

 

해당 행은 이전 행의 값을 기준으로 값이 변화한다. 

예를 들어 1행에서 A 가 1 1 2 2 2 2의 값을 가지게 된 것은 0행의 0 1 1 1 1 1에서 CA라는 최장수열을 찾게 되면서 +1이 되었다.  그리고 앞 열의 값에 영향을 받기도 한다. 0을 기준으로 공통 수열을 찾았다면 +1이 되고 그 이후의 값도 모두 +1이 된 값을 유지한다. 

 

 간단하게 말하면  같은 값을 만나면 +1을 해주고 다른 값을 만나면 이전 열이나 이전 행의 값 중 큰 값을 비교해서 넣으면 된다는 말이다. 

 

반응형

---

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = br.readLine().split("");
		String[] str2 = br.readLine().split("");
		int [][] dp = new int [str1.length+1][str2.length+1];
		
		for(int i=1; i<=str1.length;i++) {
			for(int j=1; j<=str2.length;j++) {
				if(str2[j-1].equals(str1[i-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[str1.length][str2.length]);

	}// main()
}// class Main