[Python] 백준 9251번 - LCS

문제 https://www.acmicpc.net/problem/9251

9251번: LCS

 

학교 수업에서 DP 배울 때 LCS 배웠어서 겁먹지 않고 풀 수 있었다.

수업 때 교수님이 코드까지 주신 줄 알았는데 찾아보니 코드 없이 이론만 있었어서 직접 코드 짜는데 시간이 좀 걸리긴 했다.

처음엔 아무 생각 없이 교수님이 주신 pseudo-code 보고 그냥 짜다가 DP 문제라는 걸 깨닫고 바로 노선 변경ㅋㅋ

자꾸 인덱스 에러가 나서 애 좀 먹었다.

dp 초기화 할 때 for문에서 i,j 대신 _ 사용했더니 i와 j가 각각 뭘 의미하는지 제대로 이해하지 못했다. 이 부분 때문에 i랑 j를 서로 바꿔써서 인덱스 에러가 났었다. (i => str1, j => str2)

그래서 그냥 안 헷갈리게 for문에도 제대로 i, j로 적어줬다.

 

아 맞다 그리고 input 받을 때 strip()은 처음엔 안 하고 제출했는데 틀려서 다른 분들 strip 쓰셨길래 이것 때문에 에러났나 싶어서 써봤다. 내 생각에 안 써도 되는 것 같긴 한데.. 잘 모르겠다. 그치만 귀찮으니까 그냥 넘어갈래..

 

DP... 어렵다... 그래도 이거는 할 만 했다..

 

str1 = input().strip()
str2 = input().strip()
dp = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)]

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

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