[백준] LCS

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

9251번: LCS

Dynamic programming을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

첫째 줄과 둘째 줄에 들어온 두 문자열의 최장 공통 부분수열의 길이를 출력해야 합니다.

 

<Solution>

LCS(Longest Common Subsequence)문제입니다. 

점화식을 세워서 Dynamic programming으로 해결 할 수 있습니다.

 

아이디어는 다음과 같습니다.

1. dp array를 만든다. (이때, dp array의 [i][j]는 string1의 처음에서 부터 i번째 까지, string2의 처음에서 부터 j번째 까지에서 longest common subsequence의 길이이다. ) 2. 점화식을 이용하여 해결한다    i) dp[i][j]는 만약 string1의 i번째 문자와 string2의 j번째 문자가 같다면, dp[i-1][j-1] + 1 이다.    ii) dp[i][j]는 만약 string1의 i번째 문자와 string2의 j번째 문자가 다르면, max(dp[i][j-1], dp[i-1][j-1]) 이다.

조금 더 생각해봅시다.

 

만약 string1 = 'ABC', string2 = 'BDC' 라고 생각해봅시다. 

다음과 같은 알고리즘을 따라 가는 것을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다. 

import sys

string1 = sys.stdin.readline().rstrip()
string2 = sys.stdin.readline().rstrip()

dp = [[0]*(len(string2)+1) for _ in range(len(string1)+1)]

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

print(dp[len(string1)][len(string2)])