[DP] boj 9251 - 2차원 리스트 이용하기

백준 9251은 중간 과정 값을 저장하는 리스트를 2차원으로 써야 되는 문제다.

 

실행 시간이 더 짧은 다른 사람의 풀이를 보니 문자열의 길이를 구하는 걸 변수에 할당한 다음 사용했다.

import sys

s1 = sys.stdin.readline().rstrip()
s2 = sys.stdin.readline().rstrip()

dp = [[0] * (len(s1)+1) for _ in range(len(s2)+1)]


for i in range(1, len(s2)+1):
    for j in range(1, len(s1)+1):
        if s1[j-1] == s2[i-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])