백준 9251 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍

  • 설명

    • 두 수열의 길이가 N 미만일 때, 시간 복잡도 O(N^2)으로 문제를 해결할 수 있습니다.
    • 수열 각각을 X, Y라고 함
    • D[i][j] = X[0..i]와 Y[0..j]의 공통 부분 수열의 최대 길이
    • 두 문자열의 길이를 조금씩 늘려가며 확인, 공통 부분 수열의 최대 길이를 계산
    • 점화식
      스크린샷 2020-11-06 오후 6 30 38

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    x = input()
    y = input()

    dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]

    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])