[백준 / BOJ] 9251번 : LCS

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

9251번: LCS

 

 

---

 

코드

---

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int dp[1001][1001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	string a, b;
	cin >> a >> b;

	for (size_t i = 0; i < a.length(); i++) {
		for (size_t j = 0; j < b.length(); j++) {
			if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
			else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
		}
	}

	cout << dp[a.length()][b.length()];
	return 0;
}

 

 

 

---

 

 

어떻게 풀어야 할지 너무 생각이 안나서 결국 다른 사람들의 풀이를 참고했다. 참고하고 나니 학교에서 알고리즘 수업시간에 LCS에 관해 배웠던 것이 갑자기 새록새록 기었났다.. 이래서 복습은 참 중요한 것 같다.

LCS는 Longest Common Subsequence의 약자로, 최장 공통 부분 수열을 나타내는 용어이다. 이를 구하기 위한 아이디어는 다음과 같다.

1. a[i]와 b[j]의 문자가 같다면, 이것은 곧 a[i-1]와 b[j-1] 다음으로 공통 문자가 나온다는 의미이다. 따라서 a[i]와 b[j]까지의 문자열에 대한 LCS 길이는 a[i-1]와 b[j-1]까지의 문자열에 대한 LCS길이에 1을 더한 값이다.
2. a[i]와 b[j]의 문자가 다르다면, a[i]와 b[j]까지의 문자열에 대한 LCS 길이는 a[i]와 b[j-1]까지의 문자열에 대한 LCS 길이 또는 a[i-1]와 b[j]까지의 문자열에 대한 LCS 길이 중 큰 값을 갖는다.

ACAYKP, CAPCAK 두 개의 문자열에 대해 를 과정을 표로 나타내면 아래와 같다.

	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
P	0
C	0
A	0
K	0

 

	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
C	0
A	0
K	0

 

	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
A	0
K	0

 

	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
K	0

 

	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

 

	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