[백준] 9251 LCS

문제

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

입력

s1 = 문자열
s2 = 문자열

최대 1000글자

결과

ans: Int = 가장 긴 부분 수열의 길이

해석

LCS((Longest Common Subsequence))이므로 dp가 가장 먼저 생각난다.

 

점화식

dp[n][m] = s1의 n번째 s2[m]번째 문자까지 가장 긴 부분 수열의 길이

(if \ s[i] == s[j]),  (dp[i][j] = dp[i-1][j-1] +1 )  ,같은 문자를 찾으면 바로 직전 최장 부분 수열 + 1 
(else) (dp[i][j] = max(dp[i-1][j], dp[i][j-1]) ,같은 문자가 없을 경우 이전 경우의 수에서 가장 긴 것을 저장

 

S1 = ACAYKP, S2 = CAPCAK 일 경우 dp 배열은 다음과 같다.

 

	empty	A	C	A	Y	K	P
	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

여기서 중요한 점은 첫번째 행과 첫번 째 열을 0으로 초기화 시켜놓는 것이 중요하다 , 그래야 점화식을 세울 때
1부터 계산되어 편하게 사용할 수 있다. 

 

빨간색 부분은 같은 문자를 찾앗을 때 왼쪽 대각선 값 + 1 , 여기서 왼쪽 대각선인
i-1, j-1의 의미는 서로 한칸씩 전 상태를 의미한다.

 

그리고 빨간색이 아닌 부분은 바로 직전 상황, s1의 한칸 직전인 i-1 또는 s2의 한칸 직전인 j-1 중 더 큰 것을 선택

 

코드

import Foundation

var s1 = Array(readLine()!)
var s2 = Array(readLine()!)

let len = max(s1.count, s2.count)

var dp: [[Int]] = [[Int]](repeating: [Int](repeating: 0, count: len+1), count: len+1)

var ans: Int = 0

for i in 1...s1.count {
    for j in 1...s2.count {
        
        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])
        }
        
        ans = max(ans, dp[i][j])
    }
}

print(ans)