[C++] 백준 9251번 LCS

 

다이나믹 프로그래밍 문제입니다.

 

두개의 문자열을 받은 후 가장 긴 공통 부분 수열의 길이를 찾는 문제입니다.

 

ex) ABCF ASSSSSFDE   = AF (길이 = 2)

ex) ABCD  DCBA         = A 또는 B 또는 C 또는 D (길이 = 1)

 

이문제는 2차원 배열을 이용해서 문제를 해결하였습니다.

 

■ A C A Y K P

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

 

와 같은 배열을 만듭니다. 

그리고 문자가 같은곳에 -1을 채웁니다.

 

■  A   C   A   Y   K   P

C   0   -1   0   0   0   0

A   -1   0  -1   0   0   0

P   0   0    0    0   0  -1

C   0   -1   0   0   0   0

A   -1   0  -1   0   0   0
K   0    0   0    0  -1   0

 

다음과 같이 만들어 집니다.

(0, 0) 부터 시작해서 (n, n)까지 탐색을 합니다.

현재위치가 -1이 아니면

왼쪽, 위, 대각선 왼쪽 위 중 큰 값을 현재 위치에 넣습니다.

만약 -1이면 대각선 왼쪽 위의 값을 +1한 값을 현재 위치에 넣습니다.

이를 반복해줍니다.

 

■  A   C   A   Y   K   P

C   0   1   1   1   1   1

A   -1   0  -1   0   0   0

P   0   0    0    0   0  -1

C   0   -1   0   0   0   0

A   -1   0  -1   0   0   0
K   0    0   0    0  -1   0

첫번째줄 실행 시 map

 

 

■  A   C   A   Y   K   P

C   0   1   1   1   1   1

A   1   1   2   2   2   2

P   0   0    0    0   0  -1

C   0   -1   0   0   0   0

A   -1   0  -1   0   0   0
K   0    0   0    0  -1   0

두번째줄 실행 시 map

 

 

■  A   C   A   Y   K   P

C   0   1   1   1   1   1

A   1   1   2   2   2   2

P   1   1   2   2   2   3

C   0   -1   0   0   0   0

A   -1   0  -1   0   0   0
K   0    0   0    0  -1   0

세번째줄 실행 시 map

 

 

■  A   C   A   Y   K   P

C   0   1   1   1   1   1

A   1   1   2   2   2   2

P   1   1   2   2   2   3

C   1   2   2   2   2   3

A   -1   0  -1   0   0   0
K   0    0   0    0  -1   0

네번째줄 실행 시 map

 

 

■  A   C   A   Y   K   P

C   0   1   1   1   1   1

A   1   1   2   2   2   2

P   1   1   2   2   2   3

C   1   2   2   2   2   3

A   1   2   3   3   3   3
K   0    0   0    0  -1   0

다섯번째줄 실행 시 map

 

 

■  A   C   A   Y   K   P

C   0   1   1   1   1   1

A   1   1   2   2   2   2

P   1   1   2   2   2   3

C   1   2   2   2   2   3

A   1   2   3   3   3   3
K   1   2   3   3   4   4

여섯번째줄 실행 시 map

(n, n)을 출력하면 최대길이가 출력됩니다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int map[1010][1010];
int moveX[3] = { 0, -1, -1 };
int moveY[3] = { -1, 0, -1 };


int main(int argc, char *argv[])
{
	int maxNum = 0;
	string s1;
	string s2;

	cin >> s1;
	cin >> s2;

	int width = s1.length();
	int height = s2.length();
	for (int i = 0; i <= width; ++i) {
		for (int j = 0; j <= height; ++j) {
			map[i][j] = 0;
		}
	}

	for (int i = 1; i <= width; ++i) {
		for (int j = 1; j <= height; ++j) {
			if (s1.substr(i - 1, 1) == (s2.substr(j - 1, 1))) {
				map[i][j] = -1;
			}
		}
	}

	for (int i = 1; i <= width; ++i) {
		for (int j = 1; j <= height; ++j) {
			maxNum = 0;
			for (int k = 0; k < 3; ++k) {
				int x = i + moveX[k];
				int y = j + moveY[k];
				maxNum = max(maxNum, map[x][y]);
			}
			if (map[i][j] == -1) {	// s1, s2 같은 문자일때
				map[i][j] = map[i - 1][j - 1] + 1;
			}
			else {					// 그 외
				map[i][j] = maxNum;		
			}	
		}
	}

	cout << map[width][height] << endl;

	return 0;
}