[Python][백준/BOJ] 9251번 : LCS

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

9251번: LCS

 

내 코드

a = input().rstrip()
b = input().rstrip()

dp =[[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]:
            dp[i][j] = dp[i-1][j-1] +1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
      
print(dp[-1][-1])
print(*dp)

 

코드 리뷰

잘 보지 못했던 유형이지만, 알고나면 이만큼 쉬운 것이 없는 DP 연산이다.

가장 길게 증가하는 수열 시리즈 중 하나이다. 하지만 문자로 이루어져 있으며, 두 개의 문자열을 비교하면서 같은 것의 문자 수열을 찾아내야 한다는 점에서 난이도가 높은 게 아닐까 생각한다. 

가장 길게 증가하는 수열(두 문자열의 일치하는 문자 수열 찾기)

	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

연산은 위의 표와 같이 진행된다. DP를 사용한다는 것이 특징인데, DP를 사용하는 만큼 수가 1씩 카운팅되면 그대로 끝까지 계속 끌고간다. 그래서 한 번 높아진 수는 그 이하로 더 낮아질 수가 없다.

for i in range(1, len(b)):
    for j in range(1, len(a)):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] +1

문자열 A와 문자열 B가 있으면, 같은 문자를 찾기 위해 FOR문을 돌리며 찾는다. 찾으면 그 이후로는 무조건 그 수 이상으로 높아지는 것이다.

        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

그래서 같지 않는다면  MAX 연산을 이용하여 해당 수의 이전 연산들에서 가장 큰 수를 끌고 오는 것이다.

수는 계속해서 커지기 때문에 [-1][-1] 을 해주면 가장 큰 수를 뽑아낼 수 있다.