[백준 2024/09/28] 9251번 LCS

1. 문제

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

 

2. 접근 방법

전형적인 LCS 코드를 작성하면 된다.

elif word1[j - 1] == word2[i - 1]:

 

헷갈린 부분이 있다면, elif 부분에 word1[j] == word2[i]로 작성하였던 점이다.

 

j-1 과 i-1로 하나씩 감소해 주는 이유는 배열을 (n+1) 그리고 (m+1)로 늘려서 사용하기 때문이다.

즉, n == 0 일 때, 그리고 m == 0 일 때, 0으로 채워주어, 다른 수들을 밀어주기 때문에 m 이 1일 때, i 는 0에 접근해야 하기 때문이다.

lcs라는 함수는 재귀적으로 lcs를 해결하고자 했던 것이다. 하지만, recursion error가 발생하기에, 코드를 반복문으로 재작성해 주었다.

3. 코드

def lcs(word1, word2, m, n, save):
    if m == 0 or n == 0:
        return 0

    if save[n][m] != -1:
        return save[n][m]

    elif word1[m - 1] == word2[n - 1]:
        save[n][m] = lcs(word1, word2, m - 1, n - 1, save) + 1

    else:
        save[n][m] = max(lcs(word1, word2, m - 1, n, save), lcs(word1, word2, m, n - 1, save))

    return save[n][m]


def lcs2(word1, word2, n, m, dp):
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0

            elif word1[j - 1] == word2[i - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1

            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]


if __name__ == "__main__":
    word1 = input()
    word2 = input()
    n = len(word1)
    m = len(word2)

    save = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    print(lcs2(word1, word2, n, m, save))