[Swift][DP] 백준 5582번 (공통 부분 문자열)

요구능력 : DP

 

코드설명 : 

 

LCS를  풀고오면 문제가 상당히 쉽게느껴집니다.

LCS 풀고오기

 

LCS문제와 다른점을 예시로 설명해보면

A B C 와 A D C가 있다.

LCS라면 길이가 가장 긴건 A와 C라서 2가된다.

이 문제대로라면, 길이는 1이다.

A 또는 C의 길이이다.

이 문제는 부분수열이기 때문에 같은 문자가 연속적으로 함께있어야지만, 조건이 성립한다.

LCS는 기존에 연속적이지 않아도 중간중간 같은 문자가 나타나면 길이를 더해갔지만,

공통부분문자열의 경우에는 연속해서 같은 문자가 나오지 않으면 거기서 길이를 끊어야한다.

 

점화식을 설명하면,

for문을 돌면서 x[i - 1]의 문자와 y[j - 1]의 문자를 비교하면서 만약 같다면,

부분수열이 하나 같다는 말이므로 dp[i][j]에 dp[i - 1][j - 1] + 1을 해줍니다.

dp[i - 1][j - 1]은 표를 그려보시면 아시겠지만, 이전에 구한 부분수열이 있는 위치가 됩니다.

예를들어,

ABCD

EABCD가 있다고 가정했을 때,

i = 1, j = 1의 경우에는 x[i - 1] == y[j - 1]이 성립하지 않습니다.

i = 1, j = 2의 경우에는 성립하게됩니다.

그럼 dp[0][1] + 1이 되게되는데 dp[?][0]이나 dp[0][?]의 경우 공집합과 부분수열을 만들 수는 없으므로 0의 값이 들어있습니다.

그렇다면 dp[1][2] = 1이 되게됩니다.

다음으로, i = 2, j = 3이라고 가정했을 때,

dp[2][3] = dp[1][2] + 1이 되게됩니다.

이렇게 계속해서 연속될 경우에만 +1을 해주게 됩니다.

이 때, 답을 도출하기 위해서 result = max(result, dp[i][j])를 점화식이 있는 바로 아래에 적어준 이유는 어차피 연속해서 더하게 되는 값들중 가장 큰 값만 필요하니까 연속해서 더 했을때 가장 큰 값이 정답이 되기 때문에 적어줬습니다.

 

후기 : LCS를 꼭 풀고오셔야 차이를 느낄 수 있습니다!

import Foundation
let x = readLine()!.map{String($0)}
let y = readLine()!.map{String($0)}
var dp = Array(repeating: Array(repeating: 0, count: y.count + 1), count: x.count + 1)

var result = 0
for i in 1...x.count{
    for j in 1...y.count{
        if x[i - 1] == y[j - 1]{
            dp[i][j] = dp[i - 1][j - 1] + 1
            result = max(result, dp[i][j])
        }
    }
}
print(result)