[알고리즘/파이썬] 백준 9251 - LCS

문제

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

9251번: LCS

 

풀이

ㅋㅋㅋㅋㅋ아 ㅠ 이제 번호도 외웠다 9251 LCS. 그냥 대명사 같은거다 ^ . ^ ... 

거의 풀이를 외운 수준이라 그냥 곧바로 풀었다 ^^ ..  

 

ABB

ACB

처럼 맨 뒤가 같은 경우엔 (AB,AC를 비교했을 당시의 LCS) + 1 을 저장해주면 되고

 

ABC

ABB 

처럼 맨 뒤가 다른 경우엔

AB

ABB

를 비교했을 때의 LCS와

ABC

AB

를 비교했을 때의 LCS 중에 큰 값을 고르면 된다는 아이디어를 적용하면 된다.

 

코드

word_1 = input()
word_2 = input()

len_1 = len(word_1)
len_2 = len(word_2)

dp = [[0 for _ in range(len_2+1)] for _ in range(len_1+1)]

for i in range(1,len_1+1):
    for j in range(1,len_2+1):
        if word_2[j-1] == word_1[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])