[9251] LCS

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

---

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String st1 = sc.next();
		String st2 = sc.next();
		
		int[][] DP = new int[st1.length()+1][st2.length()+1];
		
		for(int i=0; i<st1.length(); i++) {
			for(int j=0; j<st2.length(); j++) {
				if(st1.charAt(i) == st2.charAt(j)) {
					DP[i+1][j+1] = DP[i][j] + 1;
				} else {
					DP[i+1][j+1] = Math.max(DP[i][j+1], DP[i+1][j]);
				}
			}
		}
		System.out.println(DP[st1.length()][st2.length()]);
	}
}

---

LCS 는 최장 공통 부분 수열이라는 뜻으로 두 문자열이 주어졌을 때 부분 수열이 되는 문자 중 가장 긴 문자열을 찾는 문제입니다. LCS 문제는 다이나믹 프로그래밍(DP)로 접근해서 풀면 쉽게 해결할 수 있습니다. 저도 처음에 반복문을 통해 해결하려고 했는데, 어떻게 푸는지 알고리즘이 생각안나서 같이 공부하는 친구를 통해 알게 되었습니다. LCS 는 전형적으로 정해진 유형이기 때문에 풀이법을 한번 알아두고 외워야겠다고 생각했습니다. 예제로 주어진 ACAYKP 와 CAPCAK 를 예로 들어 풀어보겠습니다.

[ 문제 풀이 ]

1. 2차원 DP배열을 만들고, 가장 0 번째 행과 0 번째 열을 0으로 모두 초기화 시켜줍니다.

2. 그리고 처음 행부터 차례대로 비교를 하는데 두가지 경우가 있습니다. 

      (1) 비교하는 문자가 다른 경우

           이 경우에는 현재 인덱스의 위와 왼쪽을 확인해서 최댓값을 넣어줍니다.

      (2) 비교하는 문자가 같은 경우

          이 경우에는 현재 인덱스의 왼쪽 위 대각선의 값에 +1 을 해서 넣어줍니다.

3. 이 방식대로 2차원 DP를 채워넣고 마지막에 있는 값을 출력하면 정답입니다.

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4