C++ 백준 9251번 : LCS

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

9251번: LCS

문제

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

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

입력

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

출력

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

---

풀이

알고리즘 수업시간 때 배운 유명한 다이나믹 프로그래밍의 LCS문제, 상대적 순서를 유지하면서 뽑아야 하고 두 문자열을 가지고 2차원 배열을 채워 나가면 된다. 우리가 구하고자 하는 값은 2차원 배열의 맨 마지막 값, 즉 DP[첫번째 문자열의 사이즈][두번째 문자열의 사이즈] 이다.

만약 같은 문자이면 왼쪽 대각선 값+1, 다른 문자이면 전 열 또는 전 행의 값 중 max값을 가져오면 된다. 

예시를 통해 알아보자! 

 

예시

첫번째 행

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

• A 와 C 부분문자열 : X
• AC 와 C 부분문자열 : C
• ACA 와 C 부분문자열 : C
• ACAY 와 C 부분문자열 : C
• ACAYK 와 C 부분문자열 : C
• ACAYKP 와 C 부분문자열 : C

두번째 행

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

• A 와 CA 부분문자열 : A
• AC 와 CA 부분문자열 : A 또는 C
• ACA 와 CA 부분문자열 : CA
• ACAY 와 CA 부분문자열 : CA
• ACAYK 와 CA 부분문자열 : CA
• ACAYKP 와 CA 부분문자열 : CA

 

세번째 행

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

• A 와 CAP 부분문자열 : A
• AC 와 CAP 부분문자열 : A 또는 C
• ACA 와 CAP부분문자열 : CA
• ACAY 와 CAP 부분문자열 : CA
• ACAYK 와 CAP 부분문자열 : CA
• ACAYKP 와 CAP 부분문자열 : CAP

 

네번째 행

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

• A 와 CAPC 부분문자열 : A
• AC 와 CAPC 부분문자열 : AC
• ACA 와 CAPC 부분문자열 : CA 또는 AC
• ACAY 와 CAPC 부분문자열 : CA 또는 AC
• ACAYK 와 CAPC 부분문자열 : CA 또는 AC
• ACAYKP 와 CAPC 부분문자열 : CAP

 

다섯번째 행

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

• A 와 CAPCA 부분문자열 : A
• AC 와 CAPCA 부분문자열 : AC
• ACA 와 CAPCA 부분문자열 : ACA
• ACAY 와 CAPCA 부분문자열 : ACA
• ACAYK 와 CAPCA 부분문자열 : ACA
• ACAYKP 와 CAPCA 부분문자열 : CAP 또는 ACA

 

여섯번째 행

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

• A 와 CAPCAK 부분문자열 : A
• AC 와 CAPCAK 부분문자열 : AC
• ACA 와 CAPCAK 부분문자열 : ACA
• ACAY 와 CAPCAK 부분문자열 : ACA
• ACAYK 와 CAPCAK 부분문자열 : ACAK
• ACAYKP 와 CAPCAK 부분문자열 : ACAK

 

점화식

dp[i][j] = dp[i-1][j-1] + 1 ( 만약 두 문자가 같을 때)

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) ( 만약 두 문자가 다를 때)

을 도출할 수 있다!

---

#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001] = { 0, };

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

	string s1, s2; cin >> s1 >> s2;
	string ans="";
	for (int i = 1; i <= s1.size(); i++) {
		for (int j = 1; j <= s2.size(); j++) {

			if (s1[i - 1] == s2[j - 1]) { // 같은 문자면  대각선 값 + 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[s1.length()][s2.length()] << '\n'; // 가장 긴 공통문자열
	cout << ans << '\n';

	return 0;
} //main