백준 9251 : LCS (파이썬)

기본적인 LCS 알고리즘 문제이다.

LCS 알고리즘에 대해서는 어떤 분이 굉장히 자세히 써 놓으셨는데,

새로 배우는 입장에서 굉장히 이해가 쉽도록 그림자료까지 첨부가 되어 있어서 이해하기가 좋았다.

 

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

나도 이번에 LCS 라는 알고리즘을 처음 보았는데 위 자료를 참고하여 풀었다.

 

---

import sys
S1 = sys.stdin.readline().strip()
S2 = sys.stdin.readline().strip()
N = len(S1)
M = len(S2)
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, M + 1):
        if S1[i - 1] == S2[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[-1][-1])

---

사실 두 번 "틀렸습니다" 당했는데,

너무 당연한 사실 두 가지를 간과하였던 것이었다.

 

1. sys.stdin.readline() 을 쓰면 개행문자가 딸려 오기 때문에 뒤에 스트립을 해서 개행문자를 벗겨내야 한다.
2. 문제에서 예시 입력으로 주어진 두 문자열의 길이가 같아서 무심코 N = len(S1) 으로 두 개의 for 문을 돌려버렸다.

두 문자열의 길이가 같다는 말은 어디에도 써 있지 않고 당연한 사실이었는데 깊이 생각하지 않고 있다가 뒤통수를 얻어맞았다.