[백준] 9251 LCS

백준 9251번 LCS

다이나믹 프로그래밍 / 문자열

 

 

 

[문제]

 

저번에 '이코테'책에서 풀었던 '편집거리'문제와 아주 유사함

 

 

 

[과정]

 

다이나믹 점화식을 사용한 2차원 배열의 동적 계획법으로 푼 문제

2차원 배열(dp)를 만들어 현재 위치에서 비교해서 갱신하는 원리

 

문자열의 알파벳을 순회할 때 같은 알파벳인 경우 해당 위치의 전의 dp값 +1을 현재 위치에 저장

 

알파벳이 다른 경우 이전까지 비교한 값 중 최대값을 현재 위치에 저장

 

 

 

[소스코드]

 

# 9251 LCS

def LCS(n,m):
    h,w = len(n), len(m)
    dp = [[0] * (w+1) for _ in range(h+1)]
    for i in range(1,h+1):
        for j in range(1,w+1):
            if n[i-1] == m[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:   dp[i][j] = max(dp[i-1][j], dp[i][j-1])    
    return print(dp[-1][-1])
    
LCS(input(),input())

 

---

 

[통과]