[ 백준 9251 ] LCS (C++)

백준의 LCS(9251) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 두 개의 문자열이 주어졌을 때, 최장 공통 부분 수열(Longest Common Subsequence)을 찾는 문제이다.

   ※ 참고 ※

   - Longest Common Substring = 최장 공통 부분 문자열

   - Longest Common Subsequence = 최장 공통 부분 수열

   - "ABDFE" 와 "ABDEF" 가 있을 때

     Longest Common Substring = "BD"

     Longest Common Subsequence = "BDE"

     두개의 차이점은 연속성 ! Substring은 연속되어 있는 공통된 문자열을 의미 !

   먼저 쉬운 예로 어떻게 푸는 문제인지 알아가보자.

   문자열 "ABDEG" 와 "ABECG" 가 있다고 생각해보자. 이 때, 마지막 G에서의 값을 어떻게 구하는지 생각해보자.

   'G'라는 문자가 두 문자열에 모두 공통적으로 들어있기 때문에, "ABDE"와 "ABEC" 까지의 최장 공통 부분수열 + 1의 값을

   해주면 될 것이다.

   그렇다면 이제 마지막 G를 빼고 "ABDE"와 "ABEC"를 보고 한번 구해보자. G와 똑같이 구하려고 보니, G와 달리 가장

   마지막 문자가 'E'와 'C'로 서로 다르게 된다. 당연한 소리지만 서로 다른 문자이기 때문에 G처럼 이전의 최장 공통 부분

   수열 + 1로는 계산이 되지 않는다. 이 때는 'E'를 LCS에 포함시켰을 때의 값과, 'C'를 LCS에 포함시켰을 때의 값을

   비교해서 더 큰 값을 선택해 주면 된다.

   'E'를 선택한 경우 LCS는 "ABE", 'C'를 선택한 경우 LCS는 "AB"가 된다.

   그럼 이제 E와 C를 빼보고 해볼까?? 아니다. 위에 2가지의 경우에 대한 해결책을 확실히 알았다면 구현할 수 있을 것이다.

  

  

백준의 LCS(9251) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 두 개의 문자열이 주어졌을 때, 최장 공통 부분 수열(Longest Common Subsequence)을 찾는 문제이다.

   ※ 참고 ※

   - Longest Common Substring = 최장 공통 부분 문자열

   - Longest Common Subsequence = 최장 공통 부분 수열

   - "ABDFE" 와 "ABDEF" 가 있을 때

     Longest Common Substring = "BD"

     Longest Common Subsequence = "BDE"

     두개의 차이점은 연속성 ! Substring은 연속되어 있는 공통된 문자열을 의미 !

   먼저 쉬운 예로 어떻게 푸는 문제인지 알아가보자.

   문자열 "ABDEG" 와 "ABECG" 가 있다고 생각해보자. 이 때, 마지막 G에서의 값을 어떻게 구하는지 생각해보자.

   'G'라는 문자가 두 문자열에 모두 공통적으로 들어있기 때문에, "ABDE"와 "ABEC" 까지의 최장 공통 부분수열 + 1의 값을

   해주면 될 것이다.

   그렇다면 이제 마지막 G를 빼고 "ABDE"와 "ABEC"를 보고 한번 구해보자. G와 똑같이 구하려고 보니, G와 달리 가장

   마지막 문자가 'E'와 'C'로 서로 다르게 된다. 당연한 소리지만 서로 다른 문자이기 때문에 G처럼 이전의 최장 공통 부분

   수열 + 1로는 계산이 되지 않는다. 이 때는 'E'를 LCS에 포함시켰을 때의 값과, 'C'를 LCS에 포함시켰을 때의 값을

   비교해서 더 큰 값을 선택해 주면 된다.

   'E'를 선택한 경우 LCS는 "ABE", 'C'를 선택한 경우 LCS는 "AB"가 된다.

   그럼 이제 E와 C를 빼보고 해볼까?? 아니다. 위에 2가지의 경우에 대한 해결책을 확실히 알았다면 구현할 수 있을 것이다.

  

   정리를 한번 해보자.

   1. 만약 비교하고 있는 문자가 같으면 ??

     → 이전 까지의 LCS에서 +1을 해주면 된다 !

   2. 만약 비교하고 있는 문자가 다르면 ??

     → 이전 까지의 LCS에서 각각의 문자를 넣었을 때의 더 큰 값으로 LCS값을 갱신해준다 !

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
 
#define endl "\n"
#define MAX 1001
using namespace std;
 
char A[MAX], B[MAX];
int DP[MAX][MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> A >> B;
}
 
void Solution()
{
    int A_Size = strlen(A);
    int B_Size = strlen(B);
 
    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] = Bigger(DP[i - 1][j], DP[i][j - 1]);
            }
    
        }
    }
 
    //for (int i = 1; i <= A_Size; i++)
    //{
    //    for (int j = 1; j <= B_Size; j++)
    //    {
    //        cout << "DP[" << i << "][" << j << "] = " << DP[i][j] << " ";
    //    }
    //    cout << endl;
    //}
    cout << DP[A_Size][B_Size] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}