[백준][C++] 9251번: LCS

https://www.acmicpc.net/problem/9251

9251번: LCS

 

이 전에 풀었던 가장 긴 증가하는 부분 수열을 구하는 문제와 비슷한 문제로 두 수열 A,B이 주어졌을 때 공통으로 가지는 부분 수열 중 가장 긴 것을 찾는 문제이다.

 

이 문제 또한 동적 프로그래밍 방법으로 풀어보았다.

 

먼저 점화식을 찾기 위해 입력 예제를 통해 규칙을 찾아봤다. 

DP[i][j]를 A[i]까지와 B[j]까지의 최장 공통 부분 수열의 길이로 정의 했고 B를 하나씩 늘려가며 공통되는 수열의 길이를 저장해봤다.

 

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

 

	C	A	P	C	A	K
A	0	1	1	1	1	1
C	1	1	1	2	2	2

 

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

 

여기서는 과정을 생략했지만 B를 끝까지 비교해서 구하다보니 아래 로직을 발견하게 됐다.

1. 만약 A[i] 와 B[j]가 같다면 DP[i][j] = DP[i-1][j-1] + 1이 된다.

2. 만약 같지 않다면 DP[i-1][j]과 DP[i][j-1]값 중 더 큰 값을 DP[i][j]에 저장하면 된다.

이렇게 DP[0][0]부터 DP[A의 길이-1][B의 길이-1]까지 모두 저장해가면 된다.

 

#include <iostream>
#include <string>

using namespace std;

string A,B;
int DP[1002][1002];

int Max(int a, int b) {
	if(a>b) return a;
	else return b;
}

int main(void) {
	cin >> A >> B;
	A = "0" + A;
	B = "0" + B;
	
	for(int i=0; i<A.size(); i++) {
		for(int j=0; j<B.size(); j++) {
			if(i==0 || j==0) {
				DP[i][j]=0;
				continue;
			}
			
			if(A[i]==B[j]) {
				DP[i][j] = DP[i-1][j-1] + 1;
			} else {
				DP[i][j] = Max(DP[i][j-1], DP[i-1][j]);
			}
		}
	}
	cout << DP[A.size()-1][B.size()-1];
}

 

 

여기서 문제 풀이를 위한 잡기술?같은 건데 수열 A와 수열 B의 첫 문자에 의미없는 값을 넣어준다. 

이렇게 하는 건 1번 로직을 위함인데 의미없는 값을 넣어주지 않으면 DP[0][0] = DP[-1][-1] + 1 과 같이 인덱스 값으로 -1을 갖기 때문이다.