[9251]LCS - C++

---

풀이

LCS - 최장 공통부분 수열

 

점화식

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]);

비교하는 두 문자가 같다면 dp [i-1][j-1] + 1

비교하는 두 문자가 다르다면 dp[i-1][j], dp [i][j-1]

둘 중 큰 값을 구한다.

 

그림 설명

전체 코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

string A, B;
int dp[1003][1003];

int main(){
  init();
  cin >> A >> B;
  for(int i = 1; i <= A.length(); ++i){
    for(int j = 1; j <= B.length(); ++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.length()][B.length()];
  return 0;
}

---

문제를 풀며

처음 문제를 보고서는 도저히 감을 잡을 수 없어 힌트를 보고 푼 문제이고,

DP를 풀때마다 이렇게도 활용할 수 있구나 하고 놀라는 일이 잦은 것 같다.

밑에 참고에 붙인 링크를 통해 힌트를 얻었으며, LCS에 대해 정말 자세하게 기술되어 있으니 꼭 보도록 하자

 

 

 

참고 : https://velog.io/@emplam27/%EC%95% 8C% EA% B3% A0% EB% A6% AC% EC% A6%98-%EA% B7% B8% EB% A6% BC% EC% 9C% BC% EB% A1%9C-%EC%95% 8C% EC%95%84% EB% B3% B4% EB% 8A%94-LCS-%EC%95% 8C% EA% B3% A0% EB% A6% AC% EC% A6%98-Longest-Common-Substring% EC%99%80-Longest-Common-Subsequence#% EA% B5% AC% ED%98%84% EA% B3% BC% EC% A0%95-2

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence