[백준] 9251번 LCS

단순히 LIS(Longest Increasing Subsequence) 처럼 풀려고 하다가 엄청 헤멘 문제 입니다..

LCS를 해결하는 방식이 있습니다. 

우선 표를 통해서 먼저 설명하겠습니다. (문제에서 주어진 것 처럼 ACAYKP, CAPCAK를 활용합니다)

		A	C	A	Y	K	P
	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

최종적인 표의 모습입니다. 알면 쉽게 풀리는.. 2가지 규칙만 적용하면 끝나는 문제입니다.

1) 같은 문자가 나오면 대각 왼쪽 상단 + 1

2) 다른 문자가 나오면 max(상, 좌)

 

먼저, 각 문자 배열 + 1만큼 DP(Dynamic programming) 변수를 선언하기! (아래 그림처럼 0으로 초기화 하기 위함) 

		A	C	A	Y	K	P
	0	0	0	0	0	0	0
C	0
A	0
P	0
C	0
A	0
K	0

다음 첫줄부터 채워보면, C끼리 만난 지점에는 대각 좌상단(CA == 0) + 1 하여 1이 됩니다. 

그 옆은 위는 0, 왼쪽은 1 이므로 그 중 큰 값인 1로 채워지게 됩니다.

		A	C	A	Y	K	P
	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

마지막으로 A 줄만 한번 더 보면, 첫번째 A가 만나는 부분의 대각선은 0이므로 1,

두번째 만나는 부분의 대각선은 1이므로 2가 됩니다. 이 과정을 반복하면 맨 처음 표처럼 나오게되고,

제일 마지막의 숫자가 답이 됩니다.

		A	C	A	Y	K	P
	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
C	0
A	0
K	0

정확한 원리는 말로 설명하기가 어렵지만.. 이해는 가는 부분입니다. 

같은 문자이면 이전까지의 배열 중 최대 값에 + 1을 해주는 것이고 

다를 경우는 최대 값을 유지해주는 개념이라고 생각됩니다.

 

아래는 위 과정을 구현한 코드입니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
    string a, b;
    cin >> a >> b;
    vector<vector<int>> d(a.length() + 1, vector<int>(b.length() + 1));
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a[i - 1] == b[j - 1])
                d[i][j] = d[i - 1][j - 1] + 1;
            else
                d[i][j] = max(d[i - 1][j], d[i][j - 1]);
        }
    }
    cout << d[a.length()][b.length()];
    return 0;
}

 

질문이나 지적사항은 댓글 부탁드립니다 :)