[BOJ] 백준 9251 LCS Python

 

9251번: LCS

문제풀이
두 문자열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴것의 길이를 찾는 문제이다. 
수열은 사용자의 입력을 받으므로 될 수 있는 경우의 수는 무한에 가깝다. 따라서 이 문제는 DP로 푸는것이 적절하다.
먼저 문자열 두개를 입력받아 한 글자씩 쪼개며 각각의 list에 저장한다. 그 다음  indexError을 피하기 위해 0번째 index에 값으로 0을 넣어주고 그 다음 dp배열을 2차원배열로 선언하며 길이를 설정함과 동시에 값들을 0으로 초기화 시킨다.

문자열1과 문자열2을 순회하며 문자가 같을 때와 문자가 다를 때를 따로 처리해주어야한다. 
문자열이 같을 때)
부분 수열의 길이가 증가해야함
문자열이 다를 때)
부분 수열의 길이의 비교가 필요함

따라서 점화식은 아래와 같이 세울 수 있었다.

if string_1[i] == string_2[j]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else:
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

---

Code

from sys import stdin

input = stdin.readline


def solve():
    string_1 = list(input().rstrip())
    string_2 = list(input().rstrip())

    string_1.insert(0, 0)
    string_2.insert(0, 0)
    dp = [[0] * len(string_2) for _ in range(len(string_1))]
    for i in range(1, len(string_1)):
        for j in range(1, len(string_2)):
            if string_1[i] == string_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    print(dp[-1][-1])


solve()