백준 9251번 LCS

백준 9251번

LCS

다이나믹 프로그래밍에서 일차원 dp 배열을 이용하여 문제를 많이 푸는데
이 문제는 기본적으로 이차원 dp 배열을 통해 풀도록 되어있다.

하지만 누적 일차원 dp 배열을 이용하여 이차원을 이용하는 것보다 간단하게 해결할 수 있다.

공통 부분 수열을 파악하기 위해서는 두 문자열을 순차적으로 탐색하며
각 원소를 비교해야 한다.

ACAYKP CAPCAK 의 예시로 살펴보면

1. A, C 비교 (A는 ACAYKP의 첫번째 원소 C는 CAPCAK의 첫번째 원소)
2. A, A 비교
3. A, P 비교
4. A, C 비교
5. A, A 비교
6. A, K 비교
   ....

이것을 리스트로 나타내면

A CAPCAK => [0 1 0 0 1 0]

그 다음은 ACAYKP의 C와 비교를 하는 것이다.

이 때, CAPCAK의 두번째 C는 앞에 A가 먼저 나왔기 때문에 두번째 C와 비교할 때는 이것을 미리 알려주어야 한다.

코드로 살펴보자.

if cnt < dp[j]:
	cnt = dp[j]

이 코드를 통해서 현재 검사하는 인덱스 앞에서 이미 중복된 것으로 파악한 원소의 길이를
현재 인덱스의 dp 리스트에 미리 넣어준다.

여기서 비교연산이 들어가는 이유는 우리가 가장 긴 LCS를 구하려고 하기 때문에
중복된 부분 수열 중 더 긴 것을 추가하기 위함이다.

그 후에 같은 알파벳이 등장하는 경우 dp 값을 cnt에 더해준다.

마지막으로 dp 리스트에 저장된 값 중 가장 큰 값이 가장 긴 LCS의 길이가 된다.