mintchoco

(BOJ1958 LCS3

Link copied to clipboard

문제 설명

Link copied to clipboard
  • 여러 입력의 공통 LCS를 구하는 문제
  • 처음에는 입력을 2개씩 순차적으로 LCS를 구하는 방식으로 생각했는데, 2개씩 비교하다보면 모든 입력을 고려하지 못하는 경우가 발생한다.
  • 그래서 이 문제의 경우 3개의 입력을 한번에 확인하는 DP를 만들어 해결했다.

문제 풀이

Link copied to clipboard
S1, S2, S3 = input().strip(), input().strip(), input().strip()
l1, l2, l3 = len(S1), len(S2), len(S3)
dp = [[[0] * (l3 + 1) for _ in range(l2 + 1)] for _ in range(l1 + 1)]
for i, x in enumerate(S1):
    for j, y in enumerate(S2):
        for k, z in enumerate(S3):
            if x == y == z:
                dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
            else:
                dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
print(dp[l1 - 1][l2 - 1][l3 - 1])
  • 우선 3개의 입력에 대하여 처리할 수 있는 DP리스트를 만든다.
  • 2개의 입력에 대한 LCS를 실행하는 것 처럼 3개로 실행한다.
    • 세 입력을 순차적으로 순회하고,
    • 만약 특정 위치에서의 값이 같다면 LCS값을 업데이트 하고
    • 아니라면 최대값만 갱신한다.