[Python] 백준 9251번 문제, 최장 공통 부분 수열(LCS)

<문제 링크>

 

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

9251번: LCS

 

---

<풀이>

 

이 문제는 최장 공통 부분 수열을 그대로 적용시키면 해결할 수 있는 문제이다.

반복문의 i는 compared_str의 길이만큼 작동하며, j는 standard_str의 길이만큼 작동해 i와 j를 비교한다.

직접 손으로 돌려보기

dp[i][j]를 채우는 수식은 다음과 같다.

i == j인 경우, 전 단계의 최고 누적합에다가 +1를 한다.

i != j인 경우, 현재 수열의 누적합이나 현재 단계의 최고 누적합을 비교해 둘 중 큰 값을 취한다.

즉, 다음과 같다.

if (i == j), dp[i][j] = dp[i-1][j-1] + 1

if (i != j), dp[i][j] = max(dp[i][j-1], dp[i-1][j])

 

---

<코드>

standard_str: 비교 대상 문자열

compared_str: 최장 공통 부분 수열을 구하기 위해 비교 대상과 비교할 문자열

dp[]: 수열 누적합

---

if __name__ == '__main__':
    standard_str = input()
    compared_str = input()

    dp = [[0 for _ in range(len(standard_str)+1)] for _ in range(len(compared_str)+1)]

    # computing
    for i in range(1, len(compared_str)+1):
        for j in range(1, len(standard_str)+1):
            # 수열에 현재 단어를 추가 할 수 있으면
            if compared_str[i-1] == standard_str[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1 # 전 단계 수열 최대 길이에서 + 1
            else:
                # 전 단계 기준 최고값([i-1][j])과 현재 포커싱 중인 단어 기준 최고값([i][j-1] 중 최고값 선별
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    print(dp[len(compared_str)][len(standard_str)])