백준 9252 파이썬 python LCS 2 @@황소처럼 우직하게@@

a = input()
b = input()

dp = [[0 for i in range(len(a) + 1)] for j in range(len(b) + 1)]

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

def findit():
    ans = ''
    now = dp[-1][-1]
    y = len(dp) - 1
    x = len(dp[0]) - 1
    while now != 0:
        if dp[y][x - 1] == now - 1 and now - 1 == dp[y - 1][x]:
            ans = a[x - 1] + ans
            now -= 1
            y -= 1
            x -= 1
        else:
            if dp[y - 1][x] > dp[y][x - 1]:
                y -= 1
            else:
                x -= 1
    return ans

print(dp[-1][-1])
print(findit())

dp 배열을 만들고 그 dp 배열에서 거꾸로 올라가면서 찾는 방법입니다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

자 위에 표 보시면, 제일 오른쪽 아래 원소부터 시작하는겁니다. 

현재 값보다 위쪽, 왼쪽 값 모두 1 작다면 왼쪽위 대각선으로 이동합니다. 이 때, 현재 값의 문자열을 기록합니다.

그렇지 않다면, 위쪽 왼쪽 값중 더 큰 값이 위치한 곳으로 이동합니다.

현재 값이 0이 되면 탐색을 종료합니다.