[9251]LCS

이번 문제는 최장 공통 부분수열(LCS:Longest Common Subsequence)이다. 어떻게 동적계획법을 이용해 풀지 고민하다가 테이블에 어떻게 기록할진 떠올렸으나 코드로 구현할 방법은 떠오르지 않아 결국 인터넷을 참고하였다.

이 문제에 어떻게 접근했냐하면 우선 큰 문제를 해결하기 위한 공통된 작은 문제를 찾아내려 했다. 앞에서부터 공통된 문자를 찾기보단 뒤에서부터 찾으려 했다. 그 결과 다음과 같은 테이블을 완성했다.

	A	C	A	Y	K	P
C		3
A	4		2
P						1
C		3
A	2		2
K					1

가장 우측 하단 위치에서부터 왼쪽 행과 윗쪽 열의 안쪽에 있는 수를 증가시켜 나간다. 이렇게 접근하면 LCS를 만족하는 문자의 개수를 알아내는 실마리를 찾은거 같았다. 하지만 문제가 있었다. 어떻게 저 가장 큰 값을 코드로 구현하고 얻어낼 수 있을지가 문제였다. 왼쪽 상단부터 값을 올려나가든 우측 하단부터 값을 올려나가든 재귀함수를 통해 구해야만 할 거 같았다. 이쯤에서 다른 블로그의 풀이 방법을 보기 시작했다. 

결과적으로 코드 작성법은 내가 생각했던거와 달랐다. 우선 0번째 행과 0번째 열을 0 값으로 초기화 하고 테이블을 윗쪽부터 차례대로 순회하며 해당위치의 문자열의 값이 같은지 알아낸다. 만약 같다면 북서쪽 칸의 값에 1을 더한다. 만약 다르다면 왼쪽 칸의 값과 윗칸의 값 중 큰 값을 읽어들여 저장한다. 이렇게 하면 O(N1(첫번째 문자열 길이) X N2(두번째 문자열 길이) 의 시간복잡도로 풀 수 있다. 2차원 배열의 테이블을 하나씩 순회하면서 최종적으로 table[N1][N2]의 위치의 값을 얻어내기만 하면 된다.

위의 방법으로 테이블을 만들면 다음과 같은 테이블이 완성된다.

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

 

코드는 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

short table[1001][1001];
char a[1002];
char b[1002];
int main(){
    short temp = 0;
    short strlen1 = 0;
    short strlen2 = 0;
    //첫번째 문자열 입력 받기
    do{
        temp += 1;
        scanf("%1c", &a[temp]);
        strlen1 += 1;
    }while(a[temp] != '\n');
    temp = 0;
    //두번째 문자열 입력 받기
    do{
        temp += 1;
        scanf("%1c", &b[temp]);
        strlen2 += 1;
    }while(b[temp] != '\n');

    //2차원 테이블에 똑같은 문자가 위치한 해당 행렬에 값 표시
    for(int i = 0; i < strlen1; i++)
    {
        for(int j = 0; j < strlen2; j++)
        {
            if(i == 0 or j == 0)
                table[i][j] = 0;
            else if(a[i] == b[j])
                table[i][j] = table[i-1][j-1] + 1;
            else
                table[i][j] = max(table[i-1][j], table[i][j-1]);      
        }
    }
    
    cout << table[strlen1-1][strlen2-1] << endl;
}