9251_LCS...반례?

문제는 더보기

 

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

 

자력으로 풀지 못한 문제였다.

 

 

먼저 간단히 설명하자면, 동적계획법에 따라서 값을 저장하는 공간이 2차원 배열이어야 한다.

먼저 한번 보자.

 

ACAYKP와 CAPCAK를 비교할때 순차적으로 비교한다.

 

1.A , C

2.A , CA

3.A , CAP

...

  AC, C

  AC, CA

...

 

이런식으로 그리고 해당방식으로 하나씩 추가하면서 보다가, 동일한 알파벳이 나오면, 아래표에서 해당하는 부분의 왼쪽 대각선 부분에서 +1이되는것을 알 수 있다.

 

또한 알파벳이 다를 경우에는, 해당 칸의 위나 왼쪽에서 더 큰것을 가져오면 되는것을 볼 수 있다.

 

 

 

      A C  A Y  K  P

  [0, 0, 0, 0, 0, 0, 0]
C[0, 0, 1, 1, 1, 1, 1]
A[0, 1, 1, 1, 2, 2, 2]
P[0, 1, 2, 2, 2, 3, 3]
C[0, 1, 2, 2, 2, 3, 3]
A[0, 1, 2, 2, 2, 3, 4]
K[0, 1, 2, 3, 3, 3, 4]

 

위 표를 보았을때, 

 

 

import sys

a = sys.stdin.readline().strip().upper()
b = sys.stdin.readline().strip().upper()


result = [[0] * (len(b)+1) for i 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]:
            result[i][j] = result[i-1][j-1] + 1
        else:
            result[i][j] = max(result[i-1][j],result[i][j-1])

for i in result:
    print(i)
print(result[-1][-1])

특히, 입력으로 나오는 두 글자가 다른경우도 생길 수 있는데, 아래와 같은 반례가 생길 수 있다.

 

qsdferrfgtfsawfsefeesgdtdrgthyytfgfddsdawdwd
efvs

 

주의하고 풀면 될 것 같다.