[백준] 9251번 LCS - python 파이썬

문제

처음에는 부분 수열이라는 것을 몰라서 문제를 이해하는데 어려움을 겪었다.

문제를 이해한 후에도 어떻게 이 문제를 해결해줄지 고민을 하다가 구글링을 했다.

도움을 받은 사이트: https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

여기를 참고하면 dp를 통해서 문제를 해결하는 방법을 소개해주는데 그림을 통해서 어떻게 dp를 통해 문제를 해결하는 지 자세히 설명해주셨다.

전체적인 알고리즘은 이중 for문을 통해 두 문자열을 탐색하면서 두 문자열이 같은 경우에는

lcs[i][j] = lcs[i-1][j-1] + 1

을 통해 문자열의 길이를 하나 늘려서 저장해주고

같지 않다면

lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1])

를 통해 값을 갱신해주면 된다.

나의 코드

s1 = input()
s2 = input()

s1 = list(s1)
s2 = list(s2)
#0X0 부분은 비워주고 시작 list out of index를 방지하기 위함
lcs = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]

# 이전의 인덱스를 이용하여 값을 갱신하므로 1부터 시작(이때 0번째 부분엔 0이 삽입되어있음)
for j in range(1,len(s2)+1):
    for i in range(1,len(s1)+1):
        # 같은 문자일 때
        if s1[i-1] == s2[j-1]:
            lcs[i][j] =lcs[i-1][j-1] + 1
        else:
            lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1])

ans = 0

for l in lcs:
    if max(l) > ans:
        ans = max(l)

print(ans)

dp를 이용한 문제풀이 방식은 항상 식을 세우는 부분이 어려운 것같다...