[백준 / BOJ] C++ 9251 LCS

9251번: LCS

 

문제

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

9251번: LCS

 

 

풀이

입력된 두 문자열을 비교하면서 LCS(최장 공통 부분 수열)의 길이를 찾는 문제. 가능한 모든 경우의 수를 확인하면 시간초과가 나기 때문에 dp를 이용해 풀어야 한다.

 

예제를 통해 설명을 해보자. 비교하는 두 문자열은 "ACAYKP"와 "CAPCAK"다. 최장 공통 부분 수열은 "ACAK"로 길이는 4다.

	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

각 칸의 숫자의 의미는 LCS의 길이다. 각 행의 문자를 열을 옮기며 문자가 같은지 비교한다. 만약 문자가 같다면, 왼쪽 대각선 위의 숫자에 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

따라서 가장 오른쪽 아래 칸의 값이 LCS의 길이가 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string a, b;
  cin >> a >> b;
  int a_size = a.size();
  int b_size = b.size();
  vector<vector<int>> dp(a_size + 1, vector<int>(b_size + 1, 0));
  for (int i = 1; i <= a_size; i++)
    for (int j = 1; j <= b_size; j++)
      if (a[i - 1] == b[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[a_size][b_size];
  return 0;
}