[백준 DP] 9251번 - LCS

9251번 - LCS

 

<문제>

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

9251번: LCS

 

<문제풀이>

이 문제는 알고리즘 수업 시간에 다뤄봤던 문제라서 문제 풀이는 쉽게 할 수 있었다.

다만 코드를 작성할 때 좀 둘러둘러 작성한 느낌이 들었다. 코드를 완성했을 때는 생각보다 더더 코드가 간결하게 나와서 놀랬다. 

	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

str1 = "ACAYKP", str2 = "CAPCAK"

str1[i] == str2[j] 일 때, dp[i][j] = dp[i-1][j-1] + 1

그 외의 경우에는 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

결과 값은  dp[str1.size()][str2.size()]의 값이 된다. 

 

만약, 길이가 4인 문자열의 문자를 알고 싶을 경우에는 표에 밑줄 친 숫자를 확인하면 된다. 

표시해둔 부분은 각 숫자의 모서리 부분이다. 즉 문자열의 길이가 증가된 부분이다. 

1의 모서리 2개에서 2의 모서리로 이동할 때는 자신보다 아래에 위치한 모서리로만 이동이 가능하다.

위의 사진에서 확인해보면 LCS는 ACAK가 되고 길이는 4가 된다. 

 

<코드>

#include <iostream>
using namespace std;

int dp[1001][1001];

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

	string str1, str2;
	cin >> str1 >> 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 - 1][j], dp[i][j - 1]);
			}
		}
	}

	cout << dp[str1.size()][str2.size()] << endl;

	return 0;
}

 

<결과>

 

 

2022.01.04