[백준/C++] 9251번: LCS

9251번: LCS

---

 

 

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

9251번: LCS

 

 

 

 

 

 

코드

---

 

#include<iostream>
#include<cmath>

using namespace std;

int dp[1001][1001];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string str1, str2;
	cin >> str1;
	cin >> str2;
	for (int i = 1; i <= str1.size(); i++) {
		for (int j = 1; j <= str2.size(); j++) {
			if (str1[i - 1] == str2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		}
	}
	cout << dp[str1.size()][str2.size()];
}

 

 

 

 

풀이

---

(개인 공부라 설명이 잘못되거나 적절하지 못할 수 있음을 양해부탁드립니다.)

 

 

LCS(최장 공통 부분수열)

		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

 

str1 = ACAYKP

str2 = CAPCAK

 

str1[i]==str2[j]인 경우 왼쪽 대각선 위 값에 +1한 값을 대입

str1[i]!=str2[j]인 경우 바로 위의 값과 바로 왼쪽 값 중 더 큰 값을 대입

 

 

ex 1)

문자열 CA와 문자열 A에서 A와 A를 비교했을 때 서로 같은 문자열이므로 왼쪽 대각선에 위치한 값에 +1한 값인 1이 나온다.

(문자열 C와 공백 사이에서 최장공통부분수열 길이가 0인 상태에서 같은 문자열 A가 추가된 거라 생각하면 됨. (C, => CA, A))

 

 

ex 2)

 

문자열 C와 문자열 ACA에서 C와 A를 비교했을 때 서로 다른 문자열이므로 문자열이 AC, C인 상황과 ACA, 공백문자열인 상황에서 최장공통부분수열의 길이가 더 긴 값을 입력한다.

(AC, C에서 앞 문자열에 A가 추가된 것일 뿐이므로 ACA, C나 AC, C나 최장공통부분수열의 길이는 같음)

 

 

 

dp는 배열의 현재 인덱스에서의 상황 혹은 값이 최적의 상태(정답)라 생각하고 풀면 됩니당~