[백준] 9251번 - LCS (DP) - 결과 포함

www.acmicpc.net/problem/9251

9251번: LCS

이 문제 역시 혼자 풀지 못하고 다른 분들의 글을 참고했다.

다이나믹 프로그래밍 문제들은 간단해보이지만 다이나믹 프로그래밍을 이용해야겠다는 생각과

어떤 식으로 해결 방법을 구성할 지가 답을 보고도 쉽게 이해되지 않는다.

 

두 문자열을 비교해서 같은 부분 문자열의 최대 길이를 찾는 문제이다.

 

이전에 풀었던 증가하는 부분 수열 문제와 비슷하다고 생각해서 문자 하나씩 확인하면서 이 문자까지의 길이를 저장해야겠다는 

생각까지는 했지만 실제로 해결은 못했다.

 

A B 문자열이 있다면

A문자열 기준으로 이중 반복문을 돌면서 B 문자열의 문자들과 비교한다.

 

이 때 만약 같은 문자가 있다면 길이를 증가해야 할 것이다.

이때 메모할 배열이 필요하다.

 

지금까지 겹치는 문자가 몇 개였는지 기억할 필요가 있다.

기억하지 않는다면 모든 부분 문자열을 비교하는 방법을 이용해야 할 것이다.

 

표로 확인하는 것이 가장 이해가 잘 됐다.

 

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

위의 표를 보면 두 문자열을 한 글자씩 나누어 이차원 배열로 나타냈다.

규칙은

만약 두 글자가 같을 경우 왼쪽 대각선 위의 숫자 + 1

다를 경우 max(왼쪽 숫자, 위 숫자) 이다.

 

같으면 왼쪽 대각선 위의 숫자에 1을 더하고

다른 경우에는 왼쪽이나 위에 있는 숫자 중에 더 큰 값을 넣으면 된다.

 

왜 이런 표가 만들어졌는지를 생각해보자

 

먼저 각각의 글자가 같은지 다른지를 본다.

같다는 것은 우리가 구하려는 공통 부분 수열에 해당한다는 것이다.

카운트를 할 필요가 있다.

 

빨간색으로 표시한 2를 보자

이 때 비교한 두 부분 문자열은

ACA와 CA이다

여기서 공통되는 부분이 CA인 것을 알 수 있다.

 

표를 왼쪽에서 오른쪽으로 본다고 생각하면 CA와 AC까지 C 때문에 하나가 겹치고 있었다.

여기에 AC가 A가 추가되면서 겹치는 부분이 하나가 증가했다.

그렇기 때문에 기존의 1에서 1을 증가시킨 2가 되야한다.

 

왼쪽 대각선 기준으로 1을 증가시키는 이유는 ACA 도 AC에서 A가 추가된 것이고 CA도 C에서 A가 추가된 것이기 때문이다.

즉 AC와 C의 공통 수열의 길이에서 1을 증가시킨 값을 넣는 것이다.

 

두 문자가 다를 경우 왼쪽과 위 값중 큰 값을 넣는 이유는 앞에서 본 것과 같이 왼쪽과 위의 값이 이전까지 저장한 부분 수열의 길이이기 때문이다.

 

이런 식으로 표를 채워가다보면 마지막 칸에 있는 길이의 값이 최대의 길이이다.

a = input()
b = input()

d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        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])

print(d[len(a)][len(b)])