백준 | 9252번. LCS - 최장 공통 부분 수열 찾기 - DP 문제

🟦 백준 9252번. 최장 공통 부분 수열 찾기 (LCS)

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

9252번: LCS 2

LCS | longest common subseuence : 최장 공통 부분 수열

• 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
• 문자열과 관련된 DP는 이 문제와 비슷한 방식으로 풀이 가능한 것이 많다.
• 이 문제를 꼼꼼히 숙지하여 연습할 것

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

LCS 푸는 방법

1) LCS는 기본적으로 두 문자열을 행, 열 축으로 하는 2차원 배열을 생성해야 한다.
2) 2차원 배열 자체가 점화식이 된다.

1) 특정 자리 행/열 문자열의 값이 같다면
 => 왼쪽 대각선 위의 값 +1 
 DP[i][j] = DP[i-1][j-1] + 1;
2) 특정 자리 행/열 문자열의 값이 다르면 
 => 왼쪽 값 vs 윗값 중 max 값으로 세팅
 DP[i][j] = Math.max(DP[i-1][j], DP[i][j-1]; 

3) 최장 공통 수열의 ‘길이’ 는 DP[A.length][B.length] 값이 된다.

4) 마지막 자리부터 역으로 탐색하며 LCS에 해당하는 문자를 역으로 기록한다.

이때 이동하는 원칙도 다음과 같다.

(1) 두 행, 열 문자값 같으면 : 문자 기록 후,  왼쪽 대각선 위로 이동

(2) 두 행, 열 문자값 다르면 : 왼쪽 vs 위값 중 큰 쪽으로 이동

5) 역으로 기록한 문자를 다시 역으로 출력시킨다.

---

풀이 - 코드

• 위에 원칙대로 문제를 풀면 된다.
• BufferedReader 로 입출력 사용한 코드

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

/*RE 다시 풀기 LCS*/
public class Main {
	//static
	static long[][] DP;
	static char[] A;
	static char[] B;
	static ArrayList<Character> Path;
	
	//getText
	static void getText(int r, int c) {
		if(r==0 || c==0 ) return;
		
		if(A[r-1] == B[c-1]) {
			Path.add(A[r-1]);//문자 기록 
			getText(r-1, c-1);//이동 
		}else {
			if(DP[r-1][c] > DP[r][c-1]) {
				//왼쪽 값이 더크면 
				getText(r-1, c);//거기로 이동
			}else {
				getText(r, c-1);//위로 이동 
			}
		}
	}
	
	//실행 메인 
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
		A = br.readLine().toCharArray();
		B = br.readLine().toCharArray();
		
		DP = new long[A.length+1][B.length+1];
		Path = new ArrayList<>();
		
		//담기 
		for(int i=1; i<=A.length; i++) {
			for(int j=1; j<=B.length; j++) {
				if(A[i-1] == B[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[A.length][B.length]);
		
		//역으로 문자 탐색 시작 
		getText(A.length, B.length);
		
		//역으로 출력 
		for(int i=Path.size()-1; i>=0; i--) {
			System.out.print(Path.get(i));
		}
		System.out.println();
	}
}

• Scanner 로 입출력 사용한 코드

import java.util.ArrayList;
import java.util.Scanner;

/*LCS 문제 풀이 다시 */
public class Main {
	static char[] A;
	static char[] B;
	static long[][] DP;
	static ArrayList<Character> Path;
	
	static void getText(int r, int c) {
		if(r==0 || c==0) return;
		
		if(A[r-1] == B[c-1]) {
			Path.add(A[r-1]);
			getText(r-1, c-1);//왼쪽 대각선 위로 올라가 
		}else {
			if(DP[r-1][c] > DP[r][c-1]) {
				//왼쪽 값이 더크면
				getText(r-1, c);
			}else {
				getText(r, c-1);//위로 이동 
			}
		}
	}
	
	//실행 메인
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner kb= new Scanner(System.in);
		A = kb.next().toCharArray();
		B = kb.next().toCharArray();
		DP = new long[A.length+1][ B.length+1];
		Path = new ArrayList<>();
		
		for(int i=1; i<=A.length; i++) {
			for(int j=1; j<=B.length; j++) {
				if(A[i-1] == B[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[A.length][B.length]);
		
		getText(A.length, B.length);
		
		//역으로 문자 출력 
		for(int i=Path.size()-1; i>=0; i--) {
			System.out.print(Path.get(i));
		}
		System.out.println();
	}
}