[백준 9251번] LCS (C++)

문제링크 : https://www.acmicpc.net/problem/9251

9251번: LCS

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int dp[1001][1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    string s1, s2;
    cin >> s1 >> s2;

    for(int i=1; i<=s1.size(); i++)
    {
        for(int j=1; j<=s2.size(); j++)
        {
            if(s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1; //문자열의 값이 같다면 대각선위의 값보다 + 1
            }
            else
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]); //왼쪽과 위쪽중 큰 값 선택
            }
        }
    }

    cout << dp[s1.size()][s2.size()];
    return 0;
}

DP문제이다.

표를 이용해 직접 경우의 수를 체크해야 점화식을 확인할 수 있다.

 

아래 예제의 경우를 표로 작성해보았다.

ACAYKP
CAPCAK

 

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	C와 A LCS : 0	C와 AC LCS : 1	C와 ACA LCS : 1	C와  ACAY  LCS : 1	C와 ACAYK   LCS : 1	C와 ACAYLP LCS : 1
A	0	CA와 A LCS : 1	CA와 AC LCS : 1	CA와 ACA LCS : 2	CA와 ACAY LCS : 2	CA와 ACAYK LCS : 2	CA와 ACAYKP LCS : 2
P	0	CAP와 A LCS : 1	CAP와 AC LCS : 1	CAP와 ACA LCS : 2	CAP와 ACAY LCS : 2	CAP와 ACAYK LCS : 2	CAP와  ACAYKP LCS : 3
C	0	CAPC와 A LCS : 1	CAPC와 AC LCS : 2	CAPC와  ACA LCS : 2	CAPC와  ACAY LCS : 2	CAPC와  ACAYK LCS : 2	CAPC와  ACAYKP LCS : 3
A	0	CAPCA와 A LCS : 1	CAPCA와  AC LCS : 2	CAPCA와  ACA LCS : 3	CAPCA와  ACAY LCS : 3	CAPCA와  ACAYK LCS : 3	CAPCA와  ACAYKP LCS : 3
K	0	CAPCAK와 A LCS : 1	CAPCAK와 AC LCS : 2	CAPCAK와 ACA LCS : 3	CAPCAK와 ACAY LCS : 3	CAPCAK와 ACAYK LCS : 4	CAPCAK와 ACAYKP LCS : 4

위 표를 보면, 문자열의 각 문자가 같아지는 순간에, 왼쪽 대각선위의 값보다 1이 증가하는 것을 볼 수 있다.

이를 통해서 dp[i][j] = dp[i-1][j-1] + 1 이라는 점화식을 구할 수 있다.

 

다음으로 문자열의 각 문자가 달라지는 순간들을 보면, 왼쪽 또는 위쪽 값 중에서 큰 값을 가지는 것을 알 수 있다.

이를 통해서 dp[i][j] = max(dp[i-1][j], dp[i][j-1])이라는 점화식을 구할수 있다.