9251번 LCS

문제링크 : www.acmicpc.net/problem/9251

9251번: LCS

---

---

<알고리즘>

 1) 주어진 문자열을 A, B로 가정. CS들의 배열 cs 생성

 2) 두 문자열의 마지막 요소끼리 비교

    2-1) A[-1] == B[-1]이라면, 공통 부분 수열 CS의 일부로 채택하고, A[-1]과 B[-1] 삭제

    2-2) A[-1] != B[-1]이라면,

         2-2-1) A[-1]을 삭제하고 다시 2)로 돌아가 비교

         2-2-2) B[-1]을 삭제하고 다시 2)로 돌아가 비교

 3) 두 문자열 중 하나라도 empty가 되면 return, cs에 지금 과정에서 채택한 CS add

 4) 모든 과정이 끝나면 cs중 가장 길이가 긴 요소 찾아서 output

 

 

<구현>

 1) row = A의 길이, column = B의 길이인 2차 배열 dq 생성

    여기서 dq[i][j]의 값이 의미하는 바는 A[1~i]과 B[1~j]문자열의 LCS의 길이를 의미함

 2) A와 B의 index를 1부터 시작한다고 가정하고, dq[i][0]과 dq[0][j]를 0으로 초기화

    2-1) A[i] == B[j] 이면 dq[i-1][j-1]+1 (공통 부분을 새로 찾아서 길이 증가)

    2-2) A[i] != B[j] 이면 dq[i][j] = max(dq[i-1][j], dq[i][j-1]) (새로운 공통 부분이 없으므로 이전 값중 큰 값 가져오기)

 3) A의 끝까지, B의 끝까지 비교해서 살펴본 값인 dq[A.length][B.length] 값 return

 

 

+참고) 위키백과 : 최장 공통 부분 수열

ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 

최장 공통 부분 수열

 

 

 

메모리 : 15812 KB    시간 : 104ms

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String a= "";
		String b ="";
		try {a=bf.readLine();} catch(IOException e) {}
		try {b=bf.readLine();} catch(IOException e) {}
		char[] A = a.toCharArray();
		char[] B = b.toCharArray();
		
		int[][] dq = new int[1001][1001];
		for(int i =0;i<=A.length;i++) {
			dq[0][i] = 0;
		}
		for(int i =0;i<=B.length;i++) {
			dq[i][0] = 0;
		}
		
		for(int i = 1;i<=A.length;i++) {
			for(int j = 1;j<=B.length;j++) {
				if(A[i-1]==B[j-1]) {
					dq[i][j] = dq[i-1][j-1]+1;
				}
				else {
					dq[i][j] = Math.max(dq[i-1][j], dq[i][j-1]);
				}
			}
		}
		System.out.println(dq[A.length][B.length]);
	}
}