백준 9251 LCS 파이썬 문제풀이 (python LIS, LCS)

문제 보러가기

 

 

백준 LCS 파이썬 문제풀이

혼자 막 풀려고 했을 때는 아무리 생각해도 답이 나오지 않았다.  

 

풀이를 좀 찾아보면, 

 

끝에 있는 문자가 같으면 무조건 +1 이다. 

만약 같지 않다면, 필요없는 문자들을 끝에서부터 삭제한다.

 

2차원의 dp table에 각 축이 비교할 두 문자열이다.

 

정답 코드

M = list(str(input()))
N = list(str(input()))

dp = [[0 for _ in range(len(N) + 1)] for _ in range(len(M)+1)]

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

문자열 1에서 문자를 하나 가져오고

문자열 2에서 문자를 또 하나 가져오는 이 중 반복문에서

 

가져온 두 문자가 같다면 이전 LCS에서 +1값을 dp에 넣어준다.

즉 대각선 위의 값 +1 이다. 

 

다르다면, x좌표 혹은 y좌표 1만 작은 값 중 큰 값을 가져온다.

즉 왼쪽 혹은 위 중 큰 값을 dp에 넣는다.

 

풀이를 보더라도 다시 푼 다면, 바로 생각 날 정도는 아닌 것 같다.

다시 복습해서 익히도록 해보자.