boj 9251

“https://www.acmicpc.net/problem/9251”

from sys import stdin

word1 = stdin.readline()
word2 = stdin.readline()

w1len = len(word1)
w2len = len(word2)
wordmap = [[0] * (w1len) for _ in range(w2len)]
for i in range(w2len-1): 
    for j in range(w1len-1):
        if word2[i] == word1[j]:
            wordmap[i+1][j+1] = wordmap[i][j] + 1
        else:
            wordmap[i+1][j+1] = max(wordmap[i][j+1], wordmap[i+1][j])
print(wordmap[w2len-1][w1len-1])

notion

• 다이나믹 프로그래밍 - LCS
• 동적 프로그래밍은 이차원 배열을 사용하는 경우가 많다.
• 같은 경우 - max(wordmap[i][j], wordmap[i][j+1], wordmap[i+1][j]) + 1
• 다른 경우 - max(wordmap[i][j], wordmap[i][j+1], wordmap[i+1][j])
• 이렇게 했지만 잘못된 방법이었다.
• sass / sas 를 비교하면 4라는 값이 나왔다.
• 고로, 같은 경우 - wordmap[i][j] + 1
• 다른 경우 - max(wordmap[i][j+1], wordmap[i+1][j])