[Python/파이썬] 백준 9251번: LCS

문제

 

풀이

ACAYKP의 A와 CAPCAK의 C, CA, CAP, CAPC, CAPCAK 부분 수열의 LCS를 구한 뒤 2차원 배열에 저장.

(0, 0) : A, C의 LCS 값(0) 저장 / (1, 0) : A, CA 의 LCS 값(1) 저장 / (2, 0) : A, CAP 의 LCS 값(1) 저장

 

ACAYKP의 AC, CAPCAK의 C, CA, CAP, CAPC, CAPCAK 부분 수열의 LCS를 구한 뒤 2차원 배열에 저장.

(0, 1) : AC, C 의 LCS 값(1) 저장 / (1, 1) : AC, CA 의 LCS 값(1) 저장 / (2, 1) : AC, CAP 의 LCS 값(1) 저장

 

위 과정을 반복

 

그림에서 빨간색 글자는 최장 부분 수열

검은색 글자는 최장 부분 수열의 길이

파란색 글자는 LCS를 구하기 위한 두 부분 수열을 의미함

 

문자열 X의 i번째 문자와, 문자열 Y의 j번째 문자가 서로 같은 경우 (X[i] == Y[j])

X[i], Y[j]를 포함하기 전의 LCS에 1을 더한 값과 같다.

위 그림에서 문자열 X = AC, 문자열 Y = CAPC 일 때

X[1] == Y[3] 이므로 이때의 LCS는 C를 포함하기 전의 LCS값인 A에 C를 추가한 것 (그림의 좌표(2, 0) 참고)

따라서 X = AC, Y = CAPC 일 때의 LCS는 AC가 된다.

 

문자열 X의 i번째 문자와, 문자열 Y의 j번째 문자가 서로 다른 경우 (X[i] != Y[j])

위 그림에서 문자열 X = ACAYKP, 문자열 Y = CAPCAK 일 때

X[5] != Y[5] 이므로 이때의 LCS는

P를 포함하지 않은 ACAYK와 CAPCAK의 LCS

ACAYKP와 K를 포함하지 않은 CAPCA의 LCS 중 큰 값이 된다.

 

점화식

LCS(Xi, Yj) = LCS(Xi - 1, Yj - 1)
LCS(Xi, Yj) = max(LCS(Xi - 1, Yj), LCS(Xi, Yj - 1))

 

코드

str1 = " " + input()
str2 = " " + input()

dp = [[0] * (len(str1)) for _ in range(len(str2))]

for i in range(1, len(str2)):
      for j in range(1, len(str1)):
            if str2[i] == str1[j]:
                  dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[-1][-1])

 

마무리

DP는 아무리 풀고 풀어도 너무 어렵다...

풀어본 유형이라면 쉽게 풀리는 경우가 있지만 9251 문제와 같은 경우 비슷한 유형이 나와도 풀 자신이 없다...

여러 블로거분들의 해설을 보고 문제 이해는 하였지만... 혼자서는 도저히 못 풀었을 것이다...