백준 9251 <LCS> Python

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

---

LCS 알고리즘 기본 문제입니다.

 

두 문자열을 교차해 배열을 만들어준 뒤, 각 문자가 일치하는지 체크해줍니다.

 

[i, j] 에서 문자가 일치한다면 각 문자열의 해당 문자들의 직전 문자까지의 최대 일치 수에 1 을 더해주어야 합니다. 즉 memo[i-1, j-1] + 1 이 됩니다.

 

[i, j] 에서 문자가 일치하지 않는다면 각 문자열의 해당 문자들의 최대 일치 수 중 큰 값을 골라 적어줍니다. 즉 max(memo[i-1, j], memo[i, j-1]) 이 됩니다. 이는 공통 부분을 찾는 문제이기 때문에 단순히 일치하지 않아서 0 으로 초기화되지 않기 때문입니다.

---

import sys

input = sys.stdin.readline


def solution(strs):
    # DP 맵
    memo = [[0 for _ in range(len(strs[1])+1)] for __ in range(len(strs[0])+1)]
    # 탐색
    for i in range(1, len(memo)):
        for j in range(1, len(memo[0])):
            # 문자가 같으면
            if strs[0][i-1] == strs[1][j-1]:
                # 최대 공통 문자열 값 + 1
                memo[i][j] = memo[i-1][j-1] + 1
            
            # 문자가 다르면
            else:
                # 이전 문자들 중 최대 공통 문자열 값
                memo[i][j] = max(memo[i-1][j], memo[i][j-1])

    print(memo[-1][-1])


# 입력
strs = [input().strip() for _ in range(2)]

solution(strs)