[백준 9251] LCS

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

---

해설

이번 문제도 다이나믹 프로그래밍이다.

LCS 문제를 통해 또 한번 DP의 넓은 세계에 감탄한다.

 

LCS라는 문제로 Longest Common Subsequence 최장 공통 부분 수열의 길이를 구하는 문제이다.

 

지금부터 해설을 시작해보겠다.

예제에 맞게 ACAYKP CAPCAK 이 두 문자를 가지고 비교를 해보겠다.

 

먼저, 표를 그려주었다. ( 편의를 위해 0번 배열을 만들고, 0으로 초기화해놨다. )

 

	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A
C
A
Y
K
P

---

A부터 진행해보겠다.

 

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A
P
C
A
K

이것만 보고 저 위에 있는 1의 의미를 파악하긴 어려울 것이다.

첫번째로 세로에 있는 C는 (0 제외) A와 비교한다. C와 A 사이에 공통 부분이 없으므로 0.

두번째로 C와 C를 비교한다. C와 C가 공통이므로 1을 해준다. 즉, C와 AC까지 공통 부분이 1이 있다는 것이다.

세번째, 네번째도 마찬가지로 해준다.

---

B를 진행해보겠다.

 

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

 A와 A를 비교한다. A와 A가 공통이므로 1을 써주었다.

다음으로 A와 C 비교 - > 공통이 아니므로 그전에 있던 값을 그대로 1 적어주었다.

3번째로 A와 A 비교 -> 공통이므로 그전에 있던 값에 1을 더해줬다.

마찬가지도 똑같다.

 

위에서 노란 글자는 공통 부분일 때 증가시켜준 숫자이다.

그런데 잘 보면 왼쪽 위 즉, 대각선 +1 이 그 노랑숫자임을 알 수있다.

 

다음으로는 파란색 숫자를 보자.

파란 숫자는 공통인 부분이 아니다.

특징을 찾아보면 왼쪽에 있는 값과 위에 값의 최댓 값이 파란 숫자가 되는 것을 알 수있다.

 

이로써 점화식이 탄생한다.(너무 급하게 점화식을 탄생시킨거 같긴하다.)

arr[i] == arr[j] 라면 arr[i-1][j-1] + 1 이고,

arr[i] != arr[j] 라면 max(arr[i-1][j], arr[i][j-1]) 이다.

 

---

···

---

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

점화식을 통해 표를 다 작성했다.

위에 써놓은 설명이 많이 부족하다.

 

점화식을 통해 다시 이해하길 바란다.

 

arr[i] == arr[j] 일 때 arr[i-1][j-1] + 1 arr[i] != arr[j] 일 때 max(arr[i-1][j], arr[i][j-1])

 

 

···

 

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][1001];
int main() {
	string st1, st2;
    cin >> st1 >> st2;
	
    for(int i=1; i<=st2.size(); i++)
		for (int j = 1; j <= st1.size(); j++) {
			if (st2[i - 1] == st1[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	cout << dp[st2.size()][st1.size()]<<'\n';
}