[Python] 백준 9251 - LCS 문제 풀이

Overview

BOJ 9251번 LCS Python 문제 풀이
분류: Dynamic Programming (동적계획법)

---

문제 페이지

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

---

풀이 코드

from sys import stdin


def main():
    a, b = (stdin.readline().rstrip() for _ in range(2))

    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[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[-1][-1])


if __name__ == "__main__":
    main()

다이나믹 프로그래밍을 이용하여 풀이한다. 2중 for문을 통해 첫 번째 수열 a와 두 번째 수열 b의 길이가 i, j 일 때의 LCS 길이를 구하여 dp[i][j]에 저장한다. 만약 현재 i, j 위치에서 a, b 값이 동일하다면, dp의 인덱스 i, j보다 작은 값들 중에서 최대인 값 + 1 을 저장한다. 즉, dp[i - 1][j - 1]에 1을 더한 값이 된다. 반대로 i, j 위치에서 a, b 값이 동일하지 않다면, 이전 누적값 dp[i - 1][j], dp[i][j -1] 중에서 큰 값을 저장한다.
위 과정을 반복했을 때, dp 마지막 값이 정답이 된다.