9251번 - LCS

문제

채점 현황 (acmicpc.net)

채점 현황

풀이

두 개의 포인터 i와 j가 있을 때, ACAYKP와 CAPCAK 를 각각 A 와 B 라고 했을 때 LCS를 찾는 과정은 다음과 같을 것이다.

1. i : 0, j : 0 이고, A[i] = 'A', B[j] = 'C' 이므로, 이제 i에 1을 더한 경우와 j에 1을 더한 경우 각각을 살펴 봐야한다. 먼저 i 에 1을 더한 경우를 살펴본다.
2. i : 1, j : 0 이고, A[i] = 'C', B[j] = 'C' 이므로 i와 j 모두 1 씩 더한다.
3. i : 2, j : 1 이고, A[i] = 'A', B[j] = 'A' 이므로 i와 j 모두 1 씩 더한다.
4. i : 3, j : 2 이고, A[i] = 'Y', B[j] = 'P' 이므로, 이제 i에 1을 더한 경우와 j에 1을 더한 경우 각각을 살펴 봐야한다. 먼저 i 에 1을 더한 경우를 살펴본다.
5. 반복

위와 같이 두개의 포인터가 가리키는 문자가 서로 같다면 모두 옮기고, 다르다면 각각 옮겨봤을 때 가장 많은 공통 부분 문자열을 갖는 경우를 찾는 것이다. 따라서 다음과 같이 정리된다.

A = input()
B = input()
N,M = len(A),len(B)

dp = [[0]*(M+1) for _ in range(N+1)]

for i in range(N):
    for j in range(M):
        if B[j] == A[i]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

print(dp[N][M])