백준 22.02.28. 9251번 - LCS

stringA = input().strip().upper()
stringB = input().strip().upper()

dp = [[0] * (len(stringB)+1) for i in range(len(stringA)+1)]


for i in range(1, len(stringA)+1):
    for j in range(1, len(stringB)+1):
        if stringB[j-1] == stringA[i-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[-1][-1])

• 문자열 A와 B가 주어졌을 때, A와 B의 문자들을 일일히 비교하며 문자열의 최대 길이를 dp에 캐싱해줍니다.
  • 따라서 dp는 stringB의 길이만큼의 리스트를 stringA만큼 갖는 리스트로 만들어주었습니다.
• 이제 규칙을 찾아야합니다.

• 위 표는 두 문자열 중 한 문자열을 기준으로 캐싱했을 때 dp에 들어가는 값을 정리한 것입니다.
  • 간단히 설명하자면 행 또는 열의 길이가 해당 위치에서 가질 수 있는 최댓값입니다.
    • => 문자열의 길이가 2인데 일치하는 수열의 길이가 2를 초과할 수 없기 때문입니다.
  • 이를 토대로 일치하는 문자열이 발견되면 1씩 늘려나갑니다.
  • 여기서 알 수 있는 규칙은 값이 늘어날 때, 늘어난 값은 좌측 상단칸의 값보다 1 크다는 것입니다.
    • => dp[i][j] = dp[i-1][j-1]+1
  • 그리고 값이 늘어나지 않을 때는 캐싱된 값을 계승하며 진행되므로 행 또는 열의 이전값 중 큰 값을 계승합니다.
    • => dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• 이 규칙을 통하여 코드를 작성하면 됩니다.